Using a simple programming language as a computational model, Neil Jones has shown that a constant-factor time hierarchy exists: thus a constant-factor difference in time makes a difference in problem-solving power, u...
详细信息
Using a simple programming language as a computational model, Neil Jones has shown that a constant-factor time hierarchy exists: thus a constant-factor difference in time makes a difference in problem-solving power, unlike the situation with Turing machines. In this note we review this result and fill in the programming details in the proof, thus obtaining a precise version of the theorem with explicit constant factors. Specifically, multiplying the running time by 232 provably allows more decision problems to be solved.
In this work we prove the first Fixed-depth Size-hierarchy theorem for uniform AC(0) [circle plus]. In particular, we show that for any fixed d, the class C-d,C-k of functions that have uniform AC(0) [circle plus] for...
详细信息
ISBN:
(纸本)9781450367059
In this work we prove the first Fixed-depth Size-hierarchy theorem for uniform AC(0) [circle plus]. In particular, we show that for any fixed d, the class C-d,C-k of functions that have uniform AC(0) [circle plus] formulas of depth d and size n(k) form an infinite hierarchy. We show this by exhibiting the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC(0) [circle plus] formulas. The explicit functions are derived from the delta-Coin Problem, which is the computational problem of distinguishing between coins that are heads with probability (1 + delta)/2 or (1 - delta)/2, where delta is a parameter that is going to 0. We study the complexity of this problem and make progress on both upper bound and lower bound fronts. Upper bounds. For any constant d >= 2, we show that there are explicit monotone AC(0) formulas (i.e. made up of AND and OR gates only) solving the delta-coin problem that have depth d, size exp(O(d(1/delta)(1/(d-1)))), and sample complexity (i.e. number of inputs) poly(1/delta). This matches previous upper bounds of O'Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009) in terms of size (which is optimal) and improves the sample complexity from exp(O(d(1/delta)(1/(delta-1)))) to poly(1/delta). Lower bounds. We show that the above upper bounds are nearly tight (in terms of size) even for the significantly stronger model of AC(0) [circle plus] formulas (which are also allowed NOT and Parity gates): formally, we show that any AC(0) [circle plus] formula solving the dcoin problem must have size exp(O(d(1/delta)(1/(d-1)))). This strengthens a result of Shaltiel and Viola (SICOMP 2010), who prove a exp(O((1/ delta)(1/(d+2)))) lower bound for AC(0) [circle plus], and a lower bound of exp(O((1/delta)(1/(d-1)))) shown by Cohen, Ganor and Raz (APPROX-RANDOM 2014) for the class AC(0). The upper bound is a derandomization involving a use of Janson's inequality and classical comb
We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t(2)(n) is a time-constructible function and t2(n) grows faster than t(1)(n ...
详细信息
We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t(2)(n) is a time-constructible function and t2(n) grows faster than t(1)(n + 1), then there exists a language which can be accepted by a t(2)(n)-time nondeterministic cellular automaton but not by any t(1)(n)-time nondeterministic cellular automaton.
For certain computational models, a constant-factor time hierarchy theorem is known, showing that a constant-factor difference in time bounds makes a difference in problem-solving power (unlike the situation with Turi...
详细信息
For certain computational models, a constant-factor time hierarchy theorem is known, showing that a constant-factor difference in time bounds makes a difference in problem-solving power (unlike the situation with Turing machines). In this paper we apply the classic "translational technique" (padding) to these hierarchies and show that they are tighter than indicated by the previous proofs. (C) 2003 Published by Elsevier Science B.V.
We review a new iterative procedure to solve the low-lying states of the Schroedinger equation, done in collaboration with Richard Friedberg. For the groundstate energy, the nth order iterative energy is bounded by a ...
详细信息
We review a new iterative procedure to solve the low-lying states of the Schroedinger equation, done in collaboration with Richard Friedberg. For the groundstate energy, the nth order iterative energy is bounded by a finite limit, independent of n;thereby it avoids some of the inherent difficulties faced by the usual perturbative series expansions. For a fairly large class of problems, this new procedure can be proved to give convergent iterative solutions. These convergent solutions include the long standing difficult problem of a quartic potential with either symmetric or asymmetric minima.
We show that for all integers t >= 8 and arbitrarily small epsilon > 0, there exists a graph property Pi (which depends on epsilon) such that epsilon-testing Pi has non-adaptive query complexity Q = (Theta) over...
详细信息
ISBN:
(数字)9783642255915
ISBN:
(纸本)9783642255908
We show that for all integers t >= 8 and arbitrarily small epsilon > 0, there exists a graph property Pi (which depends on epsilon) such that epsilon-testing Pi has non-adaptive query complexity Q = (Theta) over tilde (q(2-2/t)), where q = (Theta) over tilde(epsilon(-1)) is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties. This also gives evidence that the canonical transformation of Goldreich and Trevisan is essentially optimal when converting an adaptive property tester to a non-adaptive property tester. To do so, we provide optimal adaptive and non-adaptive testers for the combined property of having maximum degree O(epsilon N) and being a blow-up collection of an arbitrary base graph H.
This paper studies the complexity of languages of finite words using automata theory. To go beyond the class of regular languages, we consider infinite automata and the notion of state complexity defined by Karp. We l...
详细信息
ISBN:
(纸本)9781450355834
This paper studies the complexity of languages of finite words using automata theory. To go beyond the class of regular languages, we consider infinite automata and the notion of state complexity defined by Karp. We look at alternating automata as introduced by Chandra, Kozen and Stockmeyer: such machines run independent computations on the word and gather their answers through boolean combinations. We devise a lower bound technique relying on boundedly generated lattices of languages, and give two applications of this technique. The first is a hierarchy theorem, stating that there are languages of arbitrarily high polynomial alternating state complexity, and the second is a linear lower bound on the alternating state complexity of the prime numbers written in binary. This second result strengthens a result of Hartmanis and Shank from 1968, which implies an exponentially worse lower bound for the same model.
暂无评论