Characterizing Valiant's algebraic complexity classes

Valiant introduced 20 years ago an algebraic complexity theory to study the complexity of polynomial families. The basic computation model used is the arithmetic circuit, which makes these classes very easy to define and open to combinatorial techniques. In this paper we gather known results and new techniques under a unifying theme, namely the restrictions imposed upon the gates of the circuit, building a hierarchy from formulas to circuits. As a consequence we get simpler proofs for known results such as the equality of the classes VNP and _VNPe${\mathrm{VNP}}_{\mathrm{e}}$ or the completeness of the Determinant for VQP, and new results such as a characterization of the classes VQP and VP (which we can also apply to the Boolean class LOGCFL) or a full answer to a conjecture in Bürgisser's book [Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics, vol. 7, Springer, Berlin, 2000]. We also show that for circuits of polynomial depth and unbounded size these models all have the same expressive power and can be used to characterize a uniform version of VNP.     

On The Approximability Of The Traveling Salesman Problem

We show that the traveling salesman problem with triangle inequality cannot be approximated with a ratio better than when the edge lengths are allowed to be asymmetric and when the edge lengths are symmetric, unless P=NP. The best previous lower bounds were and respectively. The reduction is from H?stad’s maximum satisfiability of linear equations modulo 2, and is nonconstructive. * Supported in part by NSF ITR Grant CCR-0121555. † Supported by NSF award CCR-0307536 and a Sloan foundation fellowship.     

On the complexity of Boolean matrix ranks

We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute.     

Near Optimal Separation Of Tree-Like And General Resolution

We present the best known separation between tree-like and general resolution, improving on the recent exp(n ) separation of [2]. This is done by constructing a natural family of contradictions, of size n, that have O(n)-size resolution refutations, but only exp((n/log n))- size tree-like refutations. This result implies that the most commonly used automated theorem procedures, which produce tree-like resolution refutations, will perform badly on some inputs, while other simple procedures, that produce general resolution refutations, will have polynomial run-time on these very same inputs. We show, furthermore that the gap we present is nearly optimal. Specifically, if S (S _T ) is the minimal size of a (tree-like) refutation, we prove that S _T = exp(O(S log log S/log S)).* This research was supported by Clore Foundation Doctoral Scholarship. Research supported by NSF Award CCR-0098197 and USA–Israel BSF Grant 97-00188. This research was supported by grant number 69/96 of the Israel Science Foundation, founded by the Israel Academy for Sciences and Humanities.     

A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution

We introduce a treatment of parametric estimation in which optimality of an estimator is measured in probability rather than in variance (the measure for which the strongest general results are known in statistics). Our motivation is that the quality of an approximation algorithm is measured by the probability that it fails to approximate the desired quantity within a set tolerance. We concentrate on the Gaussian distribution and show that the sample mean is the unique “best” estimator, in probability, for the mean of a Gaussian distribution. We also extend this method to general penalty functions and to multidimensional spherically symmetric Gaussians. The algorithmic significance of studying the Gaussian distribution is established by showing that determining the average matching size in a graph is #P-hard, and moreover approximating it reduces to estimating the mean of a random variable that (under some mild conditions) has a distribution closely approximating a Gaussian. This random variable is (essentially) polynomial time samplable, thereby yielding an FPRAS for the problem.     

Short propositional refutations for dense random 3CNF formulas

Random 3CNF formulas constitute an important distribution for measuring the average-case behavior of propositional proof systems. Lower bounds for random 3CNF refutations in many propositional proof systems are known. Most notable are the exponential-size resolution refutation lower bounds for random 3CNF formulas with Ω(n^1.5−ε)$\mathrm{\Omega }(n^{1.5-\epsilon })$ clauses (Chvátal and Szemerédi [14], Ben-Sasson and Wigderson [10]). On the other hand, the only known non-trivial upper bound on the size of random 3CNF refutations in a non-abstract propositional proof system is for resolution with Ω(n²/log?n)$\mathrm{\Omega }(n^2/\log ?n)$ clauses, shown by Beame et al. [6]. In this paper we show that already standard propositional proof systems, within the hierarchy of Frege proofs, admit short refutations for random 3CNF formulas, for sufficiently large clause-to-variable ratio. Specifically, we demonstrate polynomial-size propositional refutations whose lines are TC⁰${\mathit{T}\mathit{C}}^0$ formulas (i.e., TC⁰${\mathit{T}\mathit{C}}^0$-Frege proofs) for random 3CNF formulas with n   variables and Ω(n^1.4)$\mathrm{\Omega }(n^{1.4})$ clauses.     

Bootstrapping, part I

We construct models of the integers, to yield: witnessing, independence and separation results for weak systems of bounded induction.     

Subrecursive functions on partial sequences

The paper studies a domain theoretical notion of primitive recursion over partial sequences in the context of Scott domains. Based on a non-monotone coding of partial sequences, this notion supports a rich concept of parallelism in the sense of Plotkin. The complexity of these functions is analysed by a hierarchy of classes similar to the Grzegorczyk classes. The functions considered are characterised by a function algebra generated by continuity preserving operations starting from computable initial functions. Its layers are related to those above by showing , thus generalising results of Schwichtenberg/Müller and Niggl. Received: 18 November 1996     

The computable Lipschitz degrees of computably enumerable sets are not dense

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex.     

A recursion-theoretic approach to NP

An implicit characterization of the class NP is given, without using any minimization scheme. This is the first purely recursion-theoretic formulation of NP.     

On list primitive recursion and the complexity of computinginf

We present a primitive recursive programinf_with_lists computing the minimum of two natural numbersn andp (written in unary notation) and using primitive recursion on lists. This program has at first sight the required property of visiting simultaneously its inputs, so it is a counterexample to a theorem showing that such a program cannot be written in the language of primitive recursion on natural numbers, in the more general framework of primitive recursion on term algebras. However, its complexity is at leastinf(n,p)² so it does not implement the algorithm we have in mind to computeinf(n,p).     

The $\mu$-measure as a tool for classifying computational complexity

Two simply typed term systems and are considered, both for representing algorithms computing primitive recursive functions. is based on primitive recursion, on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in , called $\mu$ -measure, is employed to uniformly integrate traditional results in subrecursion theory with resource-free characterisations of sub-elementary complexity classes. Extending the Schwichtenberg and Müller characterisation of the Grzegorczyk classes for , it is shown $\mathcal{E}_{n+1} = \mathcal{R}^n_1n\ge 1\mathcal{R}^n_i$ denotes the \emph{th modified Heinermann class} based on . The proof does not refer to any machine-based computation model, unlike the Schwichtenberg and Müller proofs. This is due to the notion of modified recursion lying on top of each other provided by . By Ritchie's result, characterises the linear-space computable functions. Using the same method, a short and straightforward proof is presented, showing that characterises the polynomial time computable functions. Furthermore, the classes and coincide at and above level 2. Received: 22 September 1997 / Revised version: 12 May 1999     

A restricted computation model on Scott domains and its partial primitive recursive functionals

The paper builds on both a simply typed term system and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions and PTWP are studied that are closed under scvr. The twist are certain type 1 G?del recursors for simultaneous partial primitive recursion. Formally, denotes a function , however, is modelled such that is finite, or in other words, a partial sequence. As for PTWP, the concept of type writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP-computable functionals coincide with those definable in plus a constant for sequential minimisation. In particular, the functionals definable in denoted can be characterised by a subclass of PTWP-computable functionals denoted . Moreover, hierarchies of strictly increasing classes in the style of Heinermann and complexity classes are introduced such that . These results extend those for and PTWP [Nig94]. Finally, scvr is employed to define for each type the enumeration functional of all finite elements of . Received January 30, 1996     

<Emphasis Type="Italic">P</Emphasis>≠<Emphasis Type="Italic">NP</Emphasis> for Infinite Time Turing Machines

We state different versions of the P=?NP problem for infinite time Turing machines. It is observed that PNP collapses to the fact that there are analytic sets which are not Borel.The author thanks J. D. Hamkins, R. Schipperus, and P. Welch for comments on earlier versions of this paper. He thanks Sanders Seliverstov for pointing out an inaccuracy in the first version of the proof of Theorem 2.10.Received April 19, 2002; in revised form June 10, 2002 Published online May 16, 2003     

Reducing The Seed Length In The Nisan-Wigderson Generator*

The Nisan–Wigderson pseudo-random generator [19] was constructed to derandomize probabilistic algorithms under the assumption that there exist explicit functions which are hard for small circuits. We give the first explicit construction of a pseudo-random generator with asymptotically optimal seed length even when given a function which is hard for relatively small circuits. Generators with optimal seed length were previously known only assuming hardness for exponential size circuits [13,26]. We also give the first explicit construction of an extractor which uses asymptotically optimal seed length for random sources of arbitrary min-entropy. Our construction is the first to use the optimal seed length for sub-polynomial entropy levels. It builds on the fundamental connection between extractors and pseudo-random generators discovered by Trevisan [29], combined with the construction above. The key is a new analysis of the NW-generator [19]. We show that it fails to be pseudorandom only if a much harder function can be efficiently constructed from the given hard function. By repeatedly using this idea we get a new recursive generator, which may be viewed as a reduction from the general case of arbitrary hardness to the solved case of exponential hardness. * This paper is based on two conference papers [11,12] by the same authors. † Research Supported by NSF Award CCR-9734911, NSF Award CCR-0098197, Sloan Research Fellowship BR-3311, grant #93025 of the joint US-Czechoslovak Science and Technology Program, and USA-Israel BSF Grant 97-00188. ‡ Part of this work was done while at the Hebrew University and the Institute for advanced study. § This research was supported by grant number 69/96 of the Israel Science Foundation, founded by the Israel Academy for Sciences and Humanities and USA-Israel BSF Grant 97-00188.     

A feasible theory of truth over combinatory algebra

We define an applicative theory of truth _TPT${\mathsf{T}}_{\mathsf{PT}}$ which proves totality exactly for the polynomial time computable functions. _TPT${\mathsf{T}}_{\mathsf{PT}}$ has natural and simple axioms since nearly all its truth axioms are standard for truth theories over an applicative framework. The only exception is the axiom dealing with the word predicate. The truth predicate can only reflect elementhood in the words for terms that have smaller length than a given word. This makes it possible to achieve the very low proof-theoretic strength. Truth induction can be allowed without any constraints. For these reasons the system _TPT${\mathsf{T}}_{\mathsf{PT}}$ has the high expressive power one expects from truth theories. It allows embeddings of feasible systems of explicit mathematics and bounded arithmetic.     

The complexity of computing the tutte polynomial on transversal matroids

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersx andy. It is shown that for fixedx andy the problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersx andy satisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.     

Low upper bounds in the LR degrees

We say that A≤_LRB if every B-random real is A-random—in other words, if B has at least as much derandomization power as A. The LR reducibility is a natural weak reducibility in the context of randomness, and generalizes lowness for randomness. We study the existence and properties of upper bounds in the context of the LR degrees. In particular, we show that given two (or even finitely many) low sets, there is a low c.e. set which lies LR above both. This is very different from the situation in the Turing degrees, where Sacks’ splitting theorem shows that two low sets can join to 0^′.     

Regular Resolution Lower Bounds For The Weak Pigeonhole Principle

We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length , (for some global constant > 0).* Research supported by NSF grant CCR-9820831, US-Israel BSF grant 98-00349, and an NSERC grant. Research supported by US-Israel BSF grant 98-00349, and NSF grant CCR-9987077.