Publications related to Alternating Turing machine

Polynomial-time universality and limitations of deep learning

The goal of this paper is to characterize function distributions that general neural networks trained by descent algorithms (GD/SGD), can or cannot learn in polytime. The results are: (1) The paradigm of general neural networks trained by SGD is poly-time ...

WILEY2023

Efficient Quantum Algorithms for GHZ and W States, and Implementation on the IBM Quantum Computer

Nicolas Macris, Clément Christian Javerzac-Galy, Kenichi Komagata, Marc-André Dupertuis, Chun Lam Chan, Fabien Gremion, Jarla Thiesbrummel, Romain Fournier

Efficient deterministic algorithms are proposed with logarithmic step complexities for the generation of entangled GHZ(N) and W-N states useful for quantum networks, and an implementation on the IBM quantum computer up to N = 16 is demonstrated. Improved q ...

WILEY2019

Solving quantified linear arithmetic by counterexample-guided instantiation

Viktor Kuncak, Andrew Joseph Reynolds

This paper presents a framework to derive instantiation-based decision procedures for satisfiability of quantified formulas in first-order theories, including its correctness, implementation, and evaluation. Using this framework we derive decision procedur ...

2017

Induction for SMT Solvers

Viktor Kuncak, Andrew Joseph Reynolds

Satisfiability modulo theory solvers are increasingly being used to solve quantified formulas over structures such as integers and term algebras. Quantifier instantiation combined with ground decision procedure alone is insufficient to prove many formulas ...

Springer-Verlag Berlin2015

Tight Bounds for Asynchronous Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual ...

Association for Computing Machinery2014

A Method for the Assessment of the Optimal Parameter of Discrete-Time Switch Model

Mario Paolone, Reza Razzaghi, Chrysanthi Foti

This paper proposes a novel method for the optimal parameter selection of the discrete-time switch model used in circuit solvers that adopt the fixed admittance matrix nodal method (FAMNM) approach. As known, FAMNM-based circuit solvers allow to reach effi ...

Elsevier2014

On Induction for SMT Solvers

Viktor Kuncak, Andrew Joseph Reynolds

Satisfiability modulo theory solvers are increasingly being used to solve quantified formulas over structures such as integers and term algebras. Quantifier instantiation combined with ground decision procedure alone is insufficient to prove many formulas ...

2014

A Novel Method for the Optimal Parameter Selection of Discrete-Time Switch Model

Mario Paolone, Reza Razzaghi, Chrysanthi Foti

The paper proposes a novel method for the optimal parameter selection of the discrete-time switch model used in circuit solvers that adopt the Fixed Admittance Matrix Nodal Method (FAMNM) approach. As known, FAMNM-based circuit solvers allow to reach effic ...

The University of British Columbia2013

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Seth Gilbert, Dan Alistarh, Morteza Zadimoghaddam

We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of

n

processes with step complexity $ ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

On Complete Reasoning about Axiomatic Specifications

Viktor Kuncak, Swen Jacobs

Automated software verification tools typically accept specifications of functions in terms of pre- and postconditions. However, many properties of functional programs can be more naturally specified using a more general form of universally quantified prop ...

2010

Alternating Turing machine

Graph Chatbot

Chat with Graph Search

Polynomial-time universality and limitations of deep learning

Efficient Quantum Algorithms for GHZ and W States, and Implementation on the IBM Quantum Computer

Solving quantified linear arithmetic by counterexample-guided instantiation

Induction for SMT Solvers

Tight Bounds for Asynchronous Renaming

A Method for the Assessment of the Optimal Parameter of Discrete-Time Switch Model

On Induction for SMT Solvers

A Novel Method for the Optimal Parameter Selection of Discrete-Time Switch Model

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

On Complete Reasoning about Axiomatic Specifications

Solving quantified linear arithmetic by counterexample-guided instantiation

Polynomial-time universality and limitations of deep learning

Efficient Quantum Algorithms for GHZ and W States, and Implementation on the IBM Quantum Computer

Tight Bounds for Asynchronous Renaming

A Novel Method for the Optimal Parameter Selection of Discrete-Time Switch Model

Induction for SMT Solvers

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

On Induction for SMT Solvers

On Complete Reasoning about Axiomatic Specifications

A Method for the Assessment of the Optimal Parameter of Discrete-Time Switch Model