Resolution over parities (Res(⊕)) is a proof system introduced by Itsykson and Sokolov [MFCS ’14] as a stepping stone towards proving AC0[2]-Frege lower bounds. A recent line of work has established lower bounds against depth-restricted Res(⊕) refutations. Prior to this work, the state of the art was exponential lower bounds against depth O(N logN) Res(⊕) proved by Efremenko and Itsykson [CCC ’25], where N is the number of variables in the CNF. In this work we prove exponential lower bounds against depth O(N2−є) Res(⊕) refutations. The lifted Tseitin formula we consider has O(N) clauses of width 6, which lets the allowed depth be almost quadratic not only in the number of variables, but also in the CNF size. We also prove depth-restricted lower bounds for variants of the bit pigeonhole principle (BPHP), including an exponential lower bound for depth O(n2−є) Res(⊕) refutations of BPHP with n+1 pigeons and n holes.

We construct the first (locally computable, approximately) locally list decodable codes with rate, efficiency, and error tolerance approaching the information theoretic limit, a core regime of interest for the complexity theoretic task of hardness amplification. Our algorithms run in polylogarithmic time and sub-logarithmic depth, which together with classic constructions in the unique decoding (low-noise) regime leads to the resolution of several long-standing problems in coding and complexity theory:

In this work we observe a tight connection between three topics: $\mathrm{NC}^{0}$ cryptography, $\mathrm{NC}^{0}$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $\mathrm{NC}^{0}$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is an improvement to the best known static data structure lower bounds, breaking a barrier which has stood for several decades. Prior to our work, the best known lower bound for any explicit problem with M inputs and N queries was $S \geq N^{\frac{1}{t}}(\log M)^{1-\frac{1}{t}}$ for any setting of the word length w (where $S=$ space and $t=$ time) [1]. We prove, for the same class of explicit problems considered in [1], a quadratically stronger space lower bound of the form $S \geq \tilde{\Omega}\left(N^{\frac{2}{t}} \cdot(\log M)^{1-\frac{2}{t}} \cdot 2^{-O(w)}\right)$ for all even $t\gt0$. Second, for the restricted class of nonadaptive bit probe data structures, we improve on this lower bound polynomially: for all odd constants $t\gt1$ we give an explicit problem with N queries and $M \leq N^{O(1)}$ inputs and prove a lower bound $S \geq \Omega\left(N^{\frac{2}{t}+\epsilon_{t}}\right)$ for some constant $\epsilon_{t}\gt0$ depending only on t. Our results build off of an exciting body of work on refuting semi-random CSPs (e.g., [2]–[4]). We then utilize our explicit cell probe lower bounds to obtain the best known unconditional algorithms for $\mathrm{NC}^{0}$ range avoidance: we can solve any instance with stretch $n \mapsto m$ in polynomial time once $m \gg n^{\frac{t}{2}}$ when t is even; with the aid of an NP oracle we can solve any instance with $m\gt n^{\frac{t}{2}-\epsilon}$ when t is odd for some constant $\epsilon\gt 0$. Finally, using our main correspondence we establish some barrier results for obtaining significant improvements to our cell probe lower bounds: (i) near-optimal space lower bounds for an explicit problem with $t=4, w=1$ implies $\mathrm{EXP}^{\mathrm{NP}} \nsubseteq \mathrm{NC}^{1}$; (ii) under the widelybelieved assumption that polynomial-stretch $\mathrm{NC}^{0}$ PRGs exist, there is no natural proof of a lower bound of the form $S \geq N^{\Omega(1)}$ when $t=\omega(1), w=1$.

While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might hope to compress the object into a more succinct representation. An efficient algorithm (with respect to the compressed input size) could then lead to more efficient computations than algorithms taking the explicit, uncompressed object as input. This leads to a natural question: when does knowing the input instance has a more succinct representation make computation easier? We initiate the study of the computational complexity of problems on factored graphs: graphs that are given as a formula of products and unions on smaller graphs. For any graph problem, we define a parameterized version that takes factored graphs as input, parameterized by the number of (smaller) ordinary graphs used to construct the factored graph. In this setting, we characterize the parameterized complexity of several natural graph problems, exhibiting a variety of complexities. We show that a decision version of lexicographically first maximal independent set is XP-complete, and therefore unconditionally not fixed-parameter tractable (FPT). On the other hand, we show that clique counting is FPT. Finally, we show that reachability is XNL-complete. Moreover, XNL is contained in FPT if and only if NL is contained in some fixed polynomial time.

The replicability crisis is a major issue across nearly all areas of empirical science, calling for the formal study of replicability in statistics. Motivated in this context, [Impagliazzo, Lei, Pitassi, and Sorrell STOC 2022] introduced the notion of replicable learning algorithms, and gave basic procedures for 1-dimensional tasks including statistical queries. In this work, we study the computational and statistical cost of replicability for several fundamental high dimensional statistical tasks, including multi-hypothesis testing and mean estimation. Our main contribution establishes a computational and statistical equivalence between optimal replicable algorithms and high dimensional isoperimetric tilings. As a consequence, we obtain matching sample complexity upper and lower bounds for replicable mean estimation of distributions with bounded covariance, resolving an open problem of [Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sivakumar, and Sorrell, STOC 2023] and for the$N$-Coin Problem, resolving a problem of [Karbasi, Velegkas, Yang, and Zhou, NeurIPS 2023] up to log factors. While our equivalence is computational, allowing us to shave$\log$factors in sample complexity from the best known efficient algorithms, efficient isoperimetric tilings are not known. To circumvent this, we introduce several relaxed paradigms that do allow for sample and computationally efficient algorithms, including allowing pre-processing, adaptivity, and approximate replicability. In these cases we give efficient algorithms matching or beating the best known sample complexity for mean estimation and the coin problem, including a generic procedure that reduces the standard quadratic overhead of replicability to linear in expectation.

The notion of replicable algorithms was introduced by Impagliazzo, Lei, Pitassi, and Sorrell (STOC’22) to describe randomized algorithms that are stable under the resampling of their inputs. More precisely, a replicable algorithm gives the same output with high probability when its randomness is fixed and it is run on a new i.i.d. sample drawn from the same distribution. Using replicable algorithms for data analysis can facilitate the verification of published results by ensuring that the results of an analysis will be the same with high probability, even when that analysis is performed on a new data set.

We introduce the notion of a reproducible algorithm in the context of learning. A reproducible learning algorithm is resilient to variations in its samples — with high probability, it returns the exact same output when run on two samples from the same underlying distribution. We begin by unpacking the definition, clarifying how randomness is instrumental in balancing accuracy and reproducibility. We initiate a theory of reproducible algorithms, showing how reproducibility implies desirable properties such as data reuse and efficient testability. Despite the exceedingly strong demand of reproducibility, there are efficient reproducible algorithms for several fundamental problems in statistics and learning. First, we show that any statistical query algorithm can be made reproducible with a modest increase in sample complexity, and we use this to construct reproducible algorithms for finding approximate heavy-hitters and medians. Using these ideas, we give the first reproducible algorithm for learning halfspaces via a reproducible weak learner and a reproducible boosting algorithm. Interestingly, we utilize a connection to foams as a higher-dimension randomized rounding scheme. Finally, we initiate the study of lower bounds and inherent tradeoffs for reproducible algorithms, giving nearly tight sample complexity upper and lower bounds for reproducible versus nonreproducible SQ algorithms.

The Stabbing Planes proof system [Paul Beame et al., 2018] was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas - certain unsatisfiable systems of linear equations od 2 - which are canonical hard examples for many algebraic proof systems. In a recent (and surprising) result, Dadush and Tiwari [Daniel Dadush and Samarth Tiwari, 2020] showed that these short refutations of the Tseitin formulas could be translated into quasi-polynomial size and depth Cutting Planes proofs, refuting a long-standing conjecture. This translation raises several interesting questions. First, whether all Stabbing Planes proofs can be efficiently simulated by Cutting Planes. This would allow for the substantial analysis done on the Cutting Planes system to be lifted to practical mixed integer programming solvers. Second, whether the quasi-polynomial depth of these proofs is inherent to Cutting Planes. In this paper we make progress towards answering both of these questions. First, we show that any Stabbing Planes proof with bounded coefficients (SP*) can be translated into Cutting Planes. As a consequence of the known lower bounds for Cutting Planes, this establishes the first exponential lower bounds on SP*. Using this translation, we extend the result of Dadush and Tiwari to show that Cutting Planes has short refutations of any unsatisfiable system of linear equations over a finite field. Like the Cutting Planes proofs of Dadush and Tiwari, our refutations also incur a quasi-polynomial blow-up in depth, and we conjecture that this is inherent. As a step towards this conjecture, we develop a new geometric technique for proving lower bounds on the depth of Cutting Planes proofs. This allows us to establish the first lower bounds on the depth of Semantic Cutting Planes proofs of the Tseitin formulas.

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We also use the result to resolve the quantum analogue of the Aanderaa-Karp-Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $Q(f) = Ω(n)$, which is also optimal.

We study the problem of boosting the accuracy of a weak learner in the (distribution-independent) PAC model with Massart noise. In the Massart noise model, the label of each example $x$ is independently misclassified with probability $\eta(x) \leq \eta$, where $\eta<1/2$. The Massart model lies between the random classification noise model and the agnostic model. Our main positive result is the first computationally efficient boosting algorithm in the presence of Massart noise that achieves misclassification error arbitrarily close to $\eta$. Prior to our work, no non-trivial booster was known in this setting. Moreover, we show that this error upper bound is best possible for polynomial-time black-box boosters, under standard cryptographic assumptions. Our upper and lower bounds characterize the complexity of boosting in the distribution-independent PAC model with Massart noise. As a simple application of our positive result, we give the first efficient Massart learner for unions of high-dimensional rectangles.

Lifting arguments show that the complexity of a function in one model is essentially that of a related function (often the composition of the original function with a small function called a gadget) in a more powerful model. Lifting has been used to prove strong lower bounds in communication complexity, proof complexity, circuit complexity and many other areas. We present a lifting construction for constant depth unbounded fan-in circuits. Given a function f, we construct a function g, so that the depth d+1 circuit complexity of g, with a certain restriction on bottom fan-in, is controlled by the depth d circuit complexity of f, with the same restriction. The function g is defined as f composed with a parity function. With some quantitative losses, average-case and general depth-d circuit complexity can be reduced to circuit complexity with this bottom fan-in restriction. As a consequence, an algorithm to approximate the depth d (for any d > 3) circuit complexity of given (truth tables of) Boolean functions yields an algorithm for approximating the depth 3 circuit complexity of functions, i.e., there are quasi-polynomial time mapping reductions between various gap-versions of AC⁰-MCSP. Our lifting results rely on a blockwise switching lemma that may be of independent interest. We also show some barriers on improving the efficiency of our reductions: such improvements would yield either surprisingly efficient algorithms for MCSP or stronger than known AC⁰ circuit lower bounds.

We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogonal range search, model-checking first-order properties on geometric intersection graphs, and elementary questions on multidimensional data like verifying Pareto optimality of a choice of data points. Focusing on constant dimension d, we show that any k-quantifier, d-dimensional such problem is solvable in O(n^{k-1} log^{d-1} n) time. Furthermore, this algorithm is conditionally tight up to subpolynomial factors: we show that assuming the 3-uniform hyperclique hypothesis, there is a k-quantifier, (3k-3)-dimensional problem in this class that requires time Ω(n^{k-1-o(1)}). Towards identifying a single representative problem for this class, we study the existence of complete problems for the 3-quantifier setting (since 2-quantifier problems can already be solved in near-linear time O(nlog^{d-1} n), and k-quantifier problems with k > 3 reduce to the 3-quantifier case). We define a problem Vector Concatenated Non-Domination VCND_d (Given three sets of vectors X,Y and Z of dimension d,d and 2d, respectively, is there an x ∈ X and a y ∈ Y so that their concatenation x∘y is not dominated by any z ∈ Z, where vector u is dominated by vector v if u_i ≤ v_i for each coordinate 1 ≤ i ≤ d), and determine it as the "unique" candidate to be complete for this class (under fine-grained assumptions).

A major open problem in proof complexity is to prove superpolynomial lower bounds for AC0[p]-Frege proofs. This system is the analog of AC0 [p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years ([28, 30]), there are no significant lower bounds for AC0 [p]-Frege. Significant and extensive degree lower bounds have been obtained for a variety of subsystems of AC0[p]-Frege, including Nullstellensatz ([3]), Polynomial Calculus ([9]), and SOS ([14]). However to date there has been no progress on AC0 [p]-Frege lower bounds.

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an n-variate boolean function has circuit complexity less than a given parameter s. We prove that MCSP is hard for constant-depth circuits with mod p gates, for any prime p >= 2 (the circuit class AC^0[p]). Namely, we show that MCSP requires d-depth AC^0[p] circuits of size at least exp(N^{0.49/d}), where N=2^n is the size of an input truth table of an n-variate boolean function. Our circuit lower bound proof shows that MCSP can solve the coin problem: distinguish uniformly random N-bit strings from those generated using independent samples from a biased random coin which is 1 with probability 1/2+N^{-0.49}, and 0 otherwise. Solving the coin problem with such parameters is known to require exponentially large AC^0[p] circuits. Moreover, this also implies that MAJORITY is computable by a non-uniform AC^0 circuit of polynomial size that also has MCSP-oracle gates. The latter has a few other consequences for the complexity of MCSP, e.g., we get that any boolean function in NC^1 (i.e., computable by a polynomial-size formula) can also be computed by a non-uniform polynomial-size AC^0 circuit with MCSP-oracle gates.

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer from a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don’t know super-polynomial lower bounds but do know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can construct PRGs which are essentially best possible without in turn improving the lower bounds. More specifically, say that a circuit family has shrinkage exponent Γ if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of p Γ + o (1) . Our PRG uses a seed of length s 1/(Γ + 1) + o (1) to fool circuits in the family of size s . By using this generic construction, we get PRGs with polynomially small error for the following classes of circuits of size s and with the following seed lengths: (1) For de Morgan formulas, seed length s 1/3+ o (1) ; (2) For formulas over an arbitrary basis, seed length s 1/2+ o (1) ; (3) For read-once de Morgan formulas, seed length s .234... ; (4) For branching programs of size s , seed length s 1/2+ o (1) . The previous best PRGs known for these classes used seeds of length bigger than n /2 to output n bits, and worked only for size s = O ( n ) [8].

Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k +1 quantifiers takes time O ( m k ) and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require O ( m k −ϵ) time for any ϵ > 0. (Here, > m represents the size of the input structure, i.e., the number of tuples in all relations.) We give algorithms for every first-order property that improves this upper bound to m k /2 Θ (√ log n ) , i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. Moreover, we show that further improvement is equivalent to improving algorithms for sparse instances of the well-studied Orthogonal Vectors problem. Surprisingly, both results are obtained by showing completeness of the Sparse Orthogonal Vectors problem for the class of first-order properties under fine-grained reductions. To obtain improved algorithms, we apply the fast Orthogonal Vectors algorithm of References [3, 16]. While fine-grained reductions (reductions that closely preserve the conjectured complexities of problems) have been used to relate the hardness of disparate specific problems both within P and beyond, this is the first such completeness result for a standard complexity class.

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire. This is part of a recent line of inquiry into why arithmetic circuit complexity, despite being a heavily restricted version of Boolean complexity, still cannot prove super-linear lower bounds on general devices. One can view our work as positive news (it suffices to prove weak lower bounds to get strong ones) or negative news (it is as hard to prove weak lower bounds as it is to prove strong ones). We leave it to the reader to determine their own level of optimism.

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We show that in a number of complexity-theoretic results that use the SAT oracle, one can use the MCSP oracle instead. For example, we show that ZPEXP^{MCSP} !subseteq P/poly, which should be contrasted with the previously known circuit lower bound ZPEXP^{NP} !subseteq P/poly. We also show that, assuming the existence of Indistinguishability Obfuscators (IO), SAT and MCSP are equivalent in the sense that one has a ZPP algorithm if and only the other one does. We interpret our results as providing some evidence that MCSP may be NP-hard under randomized polynomial-time reductions.

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires n^{epsilon k} time, for some constant epsilon>1/2, to count (note that these conjectures are significantly weaker than the usual ones made on these problems) on randomized machines for all but finitely many input lengths, then we have the following derandomizations: - BPP can be decided in polynomial time using only n^alpha random bits on average over any efficient input distribution, for any constant alpha>0 - BPP can be decided in polynomial time with no randomness on average over the uniform distribution This answers an open question of Ball et al. (STOC '17) in the positive of whether derandomization can be achieved from conjectures from fine-grained complexity theory. More strongly, these derandomizations improve over all previous ones achieved from worst-case uniform assumptions by succeeding on all but finitely many input lengths. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the k-Orthogonal Vectors and k-CLIQUE problems that makes removing this restriction possible. Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions about specific problems like k-CLIQUE imply quantitative and qualitative relationships between randomized and deterministic time. This can be either viewed as a barrier to proving some of the main conjectures of fine-grained complexity theory lest we achieve a major breakthrough in unconditional derandomization or, optimistically, as route to attain such derandomizations by working on very concrete and weak conjectures about specific problems.

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by branching on an inequality and its "integer negation." That is, we can (nondeterministically choose) a hyperplane a x >= b with integer coefficients, which partitions the polytope into three pieces: the points in the polytope satisfying a x >= b, the points satisfying a x <= b-1, and the middle slab b-1 < a x < b. Since the middle slab contains no integer points it can be safely discarded, and the algorithm proceeds recursively on the other two branches. Each path terminates when the current polytope is empty, which is polynomial-time checkable. Among our results, we show somewhat surprisingly that Stabbing Planes can efficiently simulate Cutting Planes, and moreover, is strictly stronger than Cutting Planes under a reasonable conjecture. We prove linear lower bounds on the rank of Stabbing Planes refutations, by adapting a lifting argument in communication complexity.

Suppose Alice and Bob are communicating in order to compute some function f, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for f where in each round one player sends a bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkies instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). The motivation for this kind of a communication model comes from the study of the KRW conjecture. We show that for some definitions this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also prove lower bounds for these models using both combinatorial and information theoretic methods.

We generalize the "learning algorithms from natural properties" framework of [CIKK16] to get agnostic learning algorithms from natural properties with extra features. We show that if a natural property (in the sense of Razborov and Rudich [RR97]) is useful also against functions that are close to the class of "easy" functions, rather than just against "easy" functions, then it can be used to get an agnostic learning algorithm over the uniform distribution with membership queries. * For AC0[q], any prime q (constant-depth circuits of polynomial size, with AND, OR, NOT, and MODq gates of unbounded fanin), which happens to have a natural property with the requisite extra feature by [Raz87, Smo87, RR97], we obtain the first agnostic learning algorithm for AC0[q], for every prime q. Our algorithm runs in randomized quasi-polynomial time, uses membership queries, and outputs a circuit for a given Boolean function f that agrees with f on all but at most polylog(n)*opt fraction of inputs, where opt is the relative distance between f and the closest function h in the class AC0[q]. * For the ideal case, a natural proof of strongly exponential correlation circuit lower bounds against a circuit class C containing AC0[2] (i.e., circuits of size exp(Omega(n)) cannot compute some n-variate function even with exp(-Omega(n)) advantage over random guessing) would yield a polynomial-time query agnostic learning algorithm for C with the approximation error O(opt).

The Black-Box Hypothesisstates that any property of Boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an upper bound on its circuit size. If this hypothesis is true, then P neq NP. We focus on the consequences of the hypothesis being false, showing that (under general conditions on the structure of a counterexample) it implies a non-trivial algorithm for CSAT. More specifically, we show that if there is a property F of boolean functions such that F has high sensitivity on some input function f of subexponential circuit complexity (which is a sufficient condition for F being a counterexample to the Black-Box Hypothesis), then CSAT is solvable by a subexponential-size circuit family. Moreover, if such a counterexample F is symmetric, then CSAT is in Ppoly. These results provide some evidence towards the conjecture (made in this paper) that the Black-Box Hypothesis is false if and only if CSAT is easy.

Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k + 1 quantifiers takes time O(mk) and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require O(mk-∊) time for any ∊ > 0. (Here, m represents the size of the input structure, i.e. the number of tuples in all relations.) We give algorithms for every first-order property that improves this upper bound to i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. Moreover, we show that further improvement is equivalent to improving algorithms for sparse instances of the well-studied Orthogonal Vectors problem. Surprisingly, both results are obtained by showing completeness of the Sparse Orthogonal Vectors problem for the class of first-order properties under fine-grained reductions. To obtain improved algorithms, we apply the fast Orthogonal Vectors algorithm of [3, 16]. While fine-grained reductions (reductions that closely preserve the conjectured complexities of problems) have been used to relate the hardness of disparate specific problems both within P and beyond, this is the first such completeness result for a standard complexity class.

Impagliazzo and Wigderson (STOC 1997) showed that if E=DTIME(2^O(n)) requires size 2^Omega(n) circuits, then every time T constant-error randomized algorithm can be simulated deterministically in time poly(T). However, such polynomial slowdown is a deal breaker when T=2^(alpha*n), for a constant alpha>0, as is the case for some randomized algorithms for NP-complete problems. Paturi and Pudlak (STOC 2010) observed that many such algorithms are obtained from randomized time T algorithms, for T < 2^o(n), with large one-sided error 1-epsilon, for epsilon=2^(-alpha*n), that are repeated 1/epsilon times to yield a constant-error randomized algorithm running in time T/epsilon=2^((alpha+o(1))*n). We show that if E requires size 2^Omega(n) nondeterministic circuits, then there is a poly(n)-time epsilon-HSG (Hitting-Set Generator) H:{0,1}^(O(log(n)) + log(1/epsilon) -> {0,1}^n, implying that time T randomized algorithms with one-sided error 1-epsilon can be simulated in deterministic time poly(T)/epsilon. In particular, under this hardness assumption, the fastest known constant-error randomized algorithm for k-SAT (for k > 3) by Paturi et al. (J. ACM 2005) can be made deterministic with essentially the same time bound. This is the first hardness versus randomness tradeoff for algorithms for NP-complete problems. We address the necessity of our assumption by showing that HSGs with very low error imply hardness for nondeterministic circuits with "few" nondeterministic bits. Applebaum et al. (CCC 2015) showed that "black-box techniques" cannot achieve poly(n)-time computable epsilon-PRGs (Pseudo-Random Generators) for epsilon=n^-omega(1), even if we assume hardness against circuits with oracle access to an arbitrary language in the polynomial time hierarchy. We introduce weaker variants of PRGs with relative error, that do follow under the latter hardness assumption. Specifically, we say that a function G:{0,1}^r -> {0,1}^n is an (epsilon,delta)-re-PRG for a circuit C if (1-epsilon)*Pr[C(U_n)=1] - delta < Pr[C(G(U_r)=1] < (1+epsilon)*Pr[C(U_n)=1] + delta. We construct poly(n)-time computable (epsilon,delta)-re-PRGs with arbitrary polynomial stretch, epsilon=n^-O(1) and delta=2^(-n^Omega(1)). We also construct PRGs with relative error that fool non-boolean distinguishers (in the sense introduced by Dubrov and Ishai (STOC 2006)). Our techniques use ideas from Paturi and Pudlak (STOC 2010), Trevisan and Vadhan (FOCS 2000), Applebaum et al. (CCC 2015). Common themes in our proofs are "composing" a PRG/HSG with a combinatorial object such as dispersers and extractors, and the use of nondeterministic reductions in the spirit of Feige and Lund (Comp. Complexity 1997).

Based on Hastad's (1986) circuit lower bounds, Linial, Mansour, and Nisan (1993) gave a quasipolytime learning algorithm for AC^0 (constant-depth circuits with AND, OR, and NOT gates), in the PAC model over the uniform distribution. It was an open question to get a learning algorithm (of any kind) for the class of AC^0[p] circuits (constant-depth, with AND, OR, NOT, and MOD_p gates for a prime p). Our main result is a quasipolytime learning algorithm for AC^0[p] in the PAC model over the uniform distribution with membership queries. This algorithm is an application of a general connection we show to hold between natural proofs (in the sense of Razborov and Rudich (1997)) and learning algorithms. We argue that a natural proof of a circuit lower bound against any (sufficiently powerful) circuit class yields a learning algorithm for the same circuit class. As the lower bounds against AC^0[p] by Razborov (1987) and Smolensky (1987) are natural, we obtain our learning algorithm for AC^0[p].

We introduce the Nondeterministic Strong Exponential Time Hypothesis (NSETH) as a natural extension of the Strong Exponential Time Hypothesis (SETH). We show that both refuting and proving NSETH would have interesting consequences.

We give the first time-space trade-off lower bounds for resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have resolution refutations of size (and space) $T(N)= N^{\Theta(\log N)}$ (and like all formulas have another resolution refutation of space $N$) but for which no resolution refutation can simultaneously have space $S(N) = T(N)^{o(1)}$ and size $T(N)^{O(1)}$. In other words, any substantial reduction in space results in a super-polynomial increase in total size. We also show somewhat stronger time-space trade-off lower bounds for regular resolution, which are also the first to apply to superlinear space. For any function $T$ that is at most weakly exponential, $T(N) = 2^{o(N^{1/4})}$, we give a tautology that has regular resolution proofs of size and space $T(N)$, but no such proofs with space $S(N) = T(N)^{1-\Omega(1)}$ and size $T(N)^{O(1)}$. Thus, any polynomial reduction in space has a superpolynomial cost in size. These tautologies are width 4 disjunctive normal form (DNF) formulas.

We tighten the connections between circuit lower bounds and derandomization for each of the following three types of derandomization: - general derandomization of promiseBPP (connected to Boolean circuits), - derandomization of Polynomial Identity Testing (PIT) over fixed finite fields (connected to arithmetic circuit lower bounds over the same field), and - derandomization of PIT over the integers (connected to arithmetic circuit lower bounds over the integers). We show how to make these connections uniform equivalences, although at the expense of using somewhat less common versions of complexity classes and for a less studied notion of inclusion. Our main results are as follows: 1. We give the first proof that a non-trivial (nondeterministic subexponential-time) algorithm for PIT over a fixed finite field yields arithmetic circuit lower bounds. 2. We get a similar result for the case of PIT over the integers, strengthening a result of Jansen and Santhanam [JS12] (by removing the need for advice). 3. We derive a Boolean circuit lower bound for NEXP intersect coNEXP from the assumption of sufficiently strong non-deterministic derandomization of promiseBPP (without advice), as well as from the assumed existence of an NP-computable non-empty property of Boolean functions useful for proving superpolynomial circuit lower bounds (in the sense of natural proofs of [RR97]); this strengthens the related results of [IKW02]. 4. Finally, we turn all of these implications into equivalences for appropriately defined promise classes and for a notion of robust inclusion/separation (inspired by [FS11]) that lies between the classical "almost everywhere" and "infinitely often" notions.

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close analogies between it and the quantum complexity class QMA(k), but the AM(k) model is also natural in its own right. We illustrate the power of multiple Merlins by giving an AM(2) protocol for 3SAT, in which the Merlins' challenges and responses consist of only n1/2+o(1)bits each. Our protocol has the consequence that, assuming the Exponential Time Hypothesis (ETH), any algorithm for approximating a dense CSP with a polynomial-size alphabet must take n(log n)1-o(1)time. Algorithms nearly matching this lower bound are known, but their running times had never been previously explained. Brandao and Harrow have also recently used our 3SAT protocol to show quasipolynomial hardness for approximating the values of certain entangled games. In the other direction, we give a simple quasipolynomial-time approximation algorithm for free games, and use it to prove that, assuming the ETH, our 3SAT protocol is essentially optimal. More generally, we show that multiple Merlins never provide more than a polynomial advantage over one: that is, AM(k) = AM for all k=poly(n). The key to this result is a sub sampling theorem for free games, which follows from powerful results by Alon et al. And Barak et al. On sub sampling dense CSPs, and which says that the value of any free game can be closely approximated by the value of a logarithmic-sized random subgame.

For Boolean functions computed by de Morgan formulas of sub quadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on "small-degree" coefficients. For a Boolean function f : {0, 1}n→ {1, -1} computable by a de Morgan formula of size s, we show that Σ f̂ (A)2≤ exp(√sϵ/3), A⊆[n] : |A| > s1/Γ+ϵwhere Γ is the shrinkage exponent for the corresponding class of formulas: Γ = 2 for de Morgan formulas, and Γ = 1/log2(√5-1) ≈ 3.27 for read-once de Morgan formulas. We prove that this Fourier concentration is essentially optimal. As an application, we get that sub quadratic-size de Morgan formulas have negligible correlation with parity, and are learnable under the uniform distribution, and also lossily compressible, in sub exponential time. Finally, we establish the tight Θ(s1/Γ) bound on the average sensitivity of read-once formulas of size s, this mirrors the known tight bound Θ(√s) on the average sensitivity of general de Morgan formulas of size s.

Chang's lemma is a useful tool in additive combinatorics and the analysis of Boolean functions. Here we give an elementary proof using entropy. We obtain a tight constant and give a slight improvement in the case where the variables are highly biased.

We give a nontrivial algorithm for the satisfiability problem for threshold circuits of depth two with a linear number of wires which improves over exhaustive search by an exponential factor. The independently interesting problem of the feasibility of sparse 0-1 integer linear programs is a special case. To our knowledge, our algorithm is the first to achieve constant savings even for the special case of Integer Linear Programming. The key idea is to reduce the satisfiability problem to the Vector Domination problem, the problem of checking whether there are two vectors in a given collection of vectors such that one dominates the other component-wise. Our result generalizes to formulas of arbitrary constant depth. We also provide a satisfiability algorithm with constant savings for depth two circuits with symmetric gates where the total weighted fan-in is at most linear in the number of variables. One of our motivations is proving strong lower bounds for TC0 circuits, exploiting the connection (established by Williams) between satisfiability algorithms and lower bounds. Our second motivation is to explore the connection between the expressive power of the circuits and the complexity of the corresponding circuit satisfiability problem.

We obtain asymptotically sharper lower bounds on resolution complexity for k-CNF's than was known previously. We show that for any large enough k there are k-CNF's which require resolution width (1-~O(k-1/4))n, regular resolution size 2(1-~O(k-1/4))n, and general resolution size (3/2)(1-~O(k-1/4))n.

We show how to approximate any function in AC0by decision trees of much smaller height than its number of variables. More precisely, we show that any function in n variables computable by an unbounded fan-in circuit of AND, OR, and NOT gates that has size S and depth d can be approximated by a decision tree of height n - βn to within error exp(-βn), where β = β(S, d) = 2-O(d log4/5S). Our proof is constructive and we use its constructivity to derive a deterministic algorithm for #AC0SAT with multiplicative factor savings over the naive 2nS algorithm of 2-Ω(βn), when applied to any n-input AC0circuit of size S and depth d. Indeed, in the same running time we can deterministically construct a decision tree of size at most 2n-βnthat exactly computes the function given by such a circuit. Recently, Impagliazzo, Matthews, and Paturi derived an algorithm for #AC0SAT with greater savings over the naive algorithm but their algorithm is only randomized rather than deterministic. The main technical result we prove to show the above is that for every family F of k-DNF formulas in n variables and every 1poly(k)|F|, one can construct a distribution on restrictions that each set at most n/C variables such that, except with probability at most2-n/(2O(k)Clog|T|), after application of the restriction, all formulas in F simultaneously reduce to logpoly(k)|F|-juntas where an s-junta is a function whose value depends on only s of its inputs. Previously, Ajtai showed simultaneous approximations for k-DNF formulas by juntas related to the one we show but with a dependence on exp(k) rather than poly(k), resulting in a weaker height-approximation tradeoff than ours.

There has been considerable interest lately in the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between a uniform distribution over a good code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That is, such distributions are very far from each other. We strengthen their result, and show that the distance is in fact exponentially close to one. This allows us to strengthen the parameters in their application for data structure lower bounds for succinct data structures for codes. From a technical point of view, we develop new large deviation bounds for functions computed by small depth decision trees, which we then apply to obtain bounds for AC0 circuits via the switching lemma. We show that if such functions are Lipschitz on average in a certain sense, then they are in fact Lipschitz almost everywhere. This type of result falls into the extensive line of research which studies large deviation bounds for the sum of random variables, where while not independent, exhibit large deviation bounds similar to these obtained by independent random variables.

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don't know superpolynomial lower bounds but do know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can construct PRGs which are essentially best possible without in turn improving the lower bounds. More specifically, say that a circuit family has shrinkage exponent Γ if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of pΓ+o(1). Our PRG uses a seed of length s1/(Γ+1)+o(1)to fool circuits in the family of size s. By using this generic construction, we get PRGs with polynomially small error for the following classes of circuits of size s and with the following seed lengths: 1) For de Morgan formulas, seed length s1/3+o(1); 2) For formulas over an arbitrary basis, seed length s1/2+o(1); 3) For read-once de Morgan formulas, seed length s.234...; 4) For branching programs of size s, seed length s1/2+o(1). The previous best PRGs known for these classes used seeds of length bigger than n/2 to output n bits, and worked only when the size s = O(n) [1].

We consider the problem of efficiently enumerating the satisfying assignments to AC 0 circuits.We give a zeroerror randomized algorithm which takes an AC 0 circuit as input and constructs a set of restrictions which partitions {0, 1} n so that under each restriction the value of the circuit is constant.Let d denote the depth of the circuit and cn denote the number of gates.This algorithm runs in time |C|2 n(1-µ c,d ) where |C| is the size of the circuit for µ c,d ≥ 1/O[lg c + d lg d] d-1 with probability at least 1 -2 -n .As a result, we get improved exponential time algorithms for AC 0 circuit satisfiability and for counting solutions.In addition, we get an improved bound on the correlation of AC 0 circuits with parity.As an important component of our analysis, we extend the Håstad Switching Lemma to handle multiple k-cnfs and k-dnfs.

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size N that have Resolution refutations of space and size each roughly Nlog2 N (and like all formulas have Resolution refutations of space N) for which any Resolution refutation using space S and length T requires T ≥ (N0.58 log2 N/S)Ω(log log N/log log log N). By downward translation, a similar tradeoff applies to all smaller space bounds.

Abstract. Informally, an obfuscator O is an (ecient, probabilistic) \\compiler " that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is \\unintel-ligible " in some sense. Obfuscators, if they exist, would have a wide vari-ety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice’s theorem. Most of these applications are based on an interpretation of the \\unintelligibility " condition in obfuscation as mean-ing that O(P) is a \\virtual black box, " in the sense that anything one can eciently compute given O(P), one could also eciently compute given oracle access to P. In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above in-tuition, obfuscation is impossible. We prove this by constructing a family of functions F that are inherently unobfuscatable in the following sense:

The “direct-product code” of a function $f$ gives its values on all $k$-tuples $(f(x_1),\dots, f(x_k))$. This basic construct underlies “hardness amplification” in cryptography, circuit complexity, and probabilistically checkable proofs (PCPs). Goldreich and Safra [SIAM J. Comput., 29 (2000), pp. 1132--1154] pioneered its local testing and its PCP application. A recent result by Dinur and Goldenberg [Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 613--622] enabled for the first time testing proximity to this important code in the “list-decoding” regime. In particular, they give a $2$-query test which works for polynomially small success probability $1/k^{\alpha}$ and show that no such test works below success probability $1/k$. Our main result is a $3$-query test which works for exponentially small success probability $\exp({-k^{\alpha}})$. Our techniques (based on recent simplified decoding algorithms for the same code [R. Impagliazzo et al., Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 2008, pp. 579--588]) also allow us to considerably simplify the analysis of the 2-query test of [Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 613--622]. We then show how to derandomize their test, achieving a code of polynomial rate, independent of $k$, and success probability $1/k^{\alpha}$. Finally, we show the applicability of the new tests to PCPs. Starting with a 2-query PCP with a projection property over an alphabet $\Sigma$ and with soundness error $1-\delta$, Rao [Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 2008, pp. 1--10] (building on Raz's ($k$-fold) parallel repetition theorem [R. Raz, SIAM J. Comput., 27 (1998), pp. 763--803] and Holenstein's proof [T. Holenstein, Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007, pp. 411--419] obtains a new 2-query PCP over the alphabet $\Sigma^k$ with soundness error $\exp(-\delta^2 k)$. Our techniques yield a 2-query PCP with soundness error $\exp(-\delta \sqrt{k})$. Our PCP construction turns out to be essentially the same as the miss-match proof system defined and analyzed by Feige and Kilian [SIAM J. Comput., 30 (2000), pp. 324--346] but with simpler analysis and exponentially better soundness error.

Non-relativization of complexity issues can be interpreted as showing that these issues cannot be resolved by "black-box" techniques. We show that the assumption DistNP ⊆ AvgP does not imply that NP ⊆ BPP by relativizing techniques. More precisely, we give an oracle relative to which the assumption holds but the conclusion fails. Moreover, relative to our oracle, there are problems in NP ∩ Co-NP that require exponential circuit complexity. We also give an alternate version where DistNP ⊆ AvgP is true, but a problem in the second level of the polynomial hierarchy is hard on the uniform distribution.

We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity, pp. 308–322, 2005 ), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rackoff. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model; (ii) that in general our model is stronger than the BT model—a fact which is witnessed by the classical shortest paths problem; (iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that there are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.

We consider a model (BT) for backtracking algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the strength of the model, we then show its limitations by providing lower bounds for algorithms in this model for several classical problems such as interval scheduling, knapsack and satisfiability.

We consider two natural extensions of the communication complexity model that are inspired by distributed computing. In both models, two parties are equipped with synchronized discrete clocks, and we assume that a bit can be sent from one party to another in one step of time. Both models allow implicit communication, by allowing the parties to choose whether to send a bit during each step. We examine trade-offs between time (total number of possible time steps elapsed) and communication (total number of bits actually sent). In the synchronized bit model, we measure the total number of bits sent between the two parties (e.g., email). We show that, in this model, communication costs can differ from the usual communication complexity by a factor roughly logarithmic in the number of time steps, and no more than such a factor. In the synchronized connection model, both parties choose whether or not to open their end of the communication channel at each time step. An exchange of bits takes place only when both ends of the channel are open (e.g., instant messaging), in which case we say that a connection has occurred. If a party does not open its end, it does not learn whether the other party opened its channel. When we restrict the number of time steps to be polynomial in the input length, and the number of connections to be polylogarithmic in the input length, the class of problems solved with this model turns out to be roughly equivalent to the communication complexity analogue of PNP([BFS86]). Using our new model, we give what we believe to be the first lower bounds for this class, separating PNPfrom Σ2∩ Π2in the communication complexity setting. Although these models are both quite natural, they have unexpected power, and lead to a refinement of problem classifications in communication complexity.

The classical direct product theorem for circuits says that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function $f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each $x_i\in\{0,1\}^n$) is significantly harder to compute on average by slightly smaller circuits. We prove a fully uniform version of the direct product theorem with information-theoretically optimal parameters, up to constant factors. Namely, we show that for given k and $\epsilon$, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes $f^k$ on at least $\epsilon$ fraction of inputs, the algorithm A outputs with probability at least $3/4$ a list of $O(1/\epsilon)$ circuits such that at least one of the circuits on the list computes f on more than $1-\delta$ fraction of inputs, for $\delta=O((\log1/\epsilon)/k)$; moreover, each output circuit is an $\mathsf{AC}^0$ circuit (of size $\mathrm{poly}(n,k,\log1/\delta,1/\epsilon)$), with oracle access to the circuit C. Using the Goldreich–Levin decoding algorithm [O. Goldreich and L. A. Levin, A hard-core predicate for all one-way functions, in Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, Seattle, 1989, pp. 25–32], we also get a fully uniform version of Yao's XOR lemma [A. C. Yao, Theory and applications of trapdoor functions, in Proceedings of the Twenty-Third Annual IEEE Symposium on Foundations of Computer Science, Chicago, 1982, pp. 80–91] with optimal parameters, up to constant factors. Our results simplify and improve those in [R. Impagliazzo, R. Jaiswal, and V. Kabanets, Approximately list-decoding direct product codes and uniform hardness amplification, in Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, 2006, pp. 187–196]. Our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct product codes (encoding a function by its values on all k-tuples) with optimal parameters. We generalize it to a family of “derandomized” direct product codes, which we call intersection codes, where the encoding provides values of the function only on a subfamily of k-tuples. The quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. As a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of k) increase in the input length. Finally, this general setting naturally allows the decoding of concatenated codes, which further yields nearly optimal derandomized amplification.

Non-relativization of complexity issues can be interpreted as giving some evidence that these issues cannot be resolved by "black-box" techniques. In the early 1990's, a sequence of important non-relativizing results was proved, mainly using algebraic techniques. Two approaches have been proposed to understand the power and limitations of these algebraic techniques: (1) Fortnow [For94] gives a construction of a class of oracles which have a similar algebraic and logical structure, although they are arbitrarily powerful. He shows that many of the non-relativizing results proved using algebraic techniques hold for all such oracles, but he does not show, e.g., that the outcome of the "P vs. NP" question differs between different oracles in that class. (2) Aaronson and Wigderson [AW08] give definitions of algebrizing separations and collapses of complexity classes, by comparing classes relative to one oracle to classes relative to an algebraic extension of that oracle. Using these definitions, they show both that the standard collapses and separations "algebrize" and that many of the open questions in complexity fail to "algebrize", suggesting that the arithmetization technique is close to its limits. However, it is unclear how to formalize algebrization of more complicated complexity statements than collapses or separations, and whether the algebrizing statements are, e.g., closed under modus ponens so it is conceivable that several algebrizing premises could imply (in a relativizing way) a non-algebrizing conclusion. In this paper, building on the work of Arora, Impagliazzo, and Vazirani [AIV92], we propose an axiomatic approach to "algebrization", which complements and clarifies the approaches of [For94] and [AW08]. We present logical theories formalizing the notion of algebrizing techniques in the following sense: most known complexity results proved using arithmetization are provable within our theories, while many open questions are independent of the theories. So provability in the proposed theories can serve as a surrogate for provability using the arithmetization technique. Our theories extend the [AIV92] theory with a new axiom, Arithmetic Checkability which intuitively says that all NP languages have verifiers that are efficiently computable low-degree polynomials (over the integers). We show the following: (i) Arithmetic checkability holds relative to arbitrarily powerful oracles (since Fortnow's algebraic oracles from [For94] all satisfy the Arithmetic Checkability axiom). (ii) Most of the algebrizing collapses and separations from [AW08], such as IP=PSPACE, NP ⊂ ZKIP if one-way functions exist, MA-EXP ⊄ P poly, etc., are provable from Arithmetic Checkability.(iii) Many of the open complexity questions (including most of those shown to require non-algebrizing techniques in [AW08]), such as "P vs. NP", "NP vs. BPP", etc., cannot be proved from Arithmetic Checkability. (iv) Arithmetic Checkability is also insufficient to prove one known result, NEXP=MIP (although relative to an oracle satisfying Arithmetic Checkability, NEXPO restricted to poly-length queries is contained in MIPO, mirroring a similar result from [AW08]).

The "direct product code" of a function f gives its values on all k-tuples (f(x1),...,f(xk)). This basic construct underlies "hardness amplification" in cryptography, circuit complexity and PCPs. Goldreich and Safra [12] pioneered its local testing and its PCP application. A recent result by Dinur and Goldenberg [5] enabled for the first time testing proximity to this important code in the "list-decoding" regime. In particular, they give a 2-query test which works for polynomially small success probability 1/kα, and show that no such test works below success probability 1/k. Our main result is a 3-query test which works for exponentially small success probability exp(-kα). Our techniques (based on recent simplified decoding algorithms for the same code [15]) also allow us to considerably simplify the analysis of the 2-query test of [5]. We then show how to derandomize their test, achieving a code of polynomial rate, independent of k, and success probability 1/kα. Finally we show the applicability of the new tests to PCPs. Starting with a 2-query PCP over an alphabet Σ and with soundness error 1-δ, Rao [19] (building on Raz's (k-fold) parallel repetition theorem [20] and Holenstein's proof [13]) obtains a new 2-query PCP over the alphabet Σk with soundness error exp(-δ2 k). Our techniques yield a 2-query PCP with soundness error exp(-δ √k). Our PCP construction turns out to be essentially the same as the miss-match proof system defined and analyzed by Feige and Kilian [8], but with simpler analysis and exponentially better soundness error.

Given a message $msg\in\{0,1\}^N$, its k-wise direct product encoding is the sequence of k-tuples $(msg(i_1),\dots,msg(i_k))$ over all possible k-tuples of indices $(i_1,\dots,i_k)\in\{1,\dots,N\}^k$. We give an efficient randomized algorithm for approximate local list-decoding of direct product codes. That is, given oracle access to a word which agrees with a k-wise direct product encoding of some message $msg\in\{0,1\}^N$ in at least $\epsilon\geqslant{poly}(1/k)$ fraction of positions, our algorithm outputs a list of ${poly}(1/\epsilon)$ strings that contains at least one string $msg'$ which is equal to $msg$ in all but at most $k^{-\Omega(1)}$ fraction of positions. The decoding is local in that our algorithm outputs a list of Boolean circuits so that the jth bit of the ith output string can be computed by running the ith circuit on input j. The running time of the algorithm is polynomial in $\log N$ and $1/\epsilon$. In general, when $\epsilon>e^{-k^{\alpha}}$ for a sufficiently small constant $\alpha>0$, we get a randomized approximate list-decoding algorithm that runs in time quasi-polynomial in $1/\epsilon$, i.e., $(1/\epsilon)^{{poly}\log1/\epsilon}$. As an application of our decoding algorithm, we get uniform hardness amplification for ${P}^{{NP}_{\parallel}}$, the class of languages reducible to ${NP}$ through one round of parallel oracle queries: If there is a language in ${P}^{{NP}_{\parallel}}$ that cannot be decided by any ${BPP}$ algorithm on more than $1-1/n^{\Omega(1)}$ fraction of inputs, then there is another language in ${P}^{{NP}_{\parallel}}$ that cannot be decided by any ${BPP}$ algorithm on more than $1/2+1/n^{\omega(1)}$ fraction of inputs.

The classical Direct-Product Theorem for circuits says that if a Boolean function f: {0,1}n -> {0,1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function fk(x1,...,xk)=(f(x1),...,f(xk)) (where each xi -> {0,1}n) is significantly harder to compute on average by slightly smaller circuits. We prove a fully uniform version of the Direct-Product Theorem with information-theoretically optimal parameters, up to constant factors. Namely, we show that for given k and ε, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes fk on at least ε fraction of inputs, the algorithm A outputs with probability at least 3/4 a list of O(1/ε) circuits such that at least one of the circuits on the list computes f on more than 1-δ fraction of inputs, for δ = O((log 1/ε)/k). Moreover, each output circuit is an AC0 circuit (of size poly(n,k,log 1/δ,1/ε)), with oracle access to the circuit C. Using the Goldreich-Levin decoding algorithm [5], we also get a fully uniform version of Yao's XOR Lemma [18] with optimal parameters, up to constant factors. Our results simplify and improve those in [10]. Our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct-product codes (encoding a function by its values on all k-tuples) with optimal parameters. We generalize it to a family of "derandomized" direct-product codes, which we call intersection codes, where the encoding provides values of the function only on a subfamily of k-tuples. The quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. As a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of k) increase in the input length. Finally, this general setting naturally allows the decoding of concatenated codes, which further yields nearly optimal derandomized amplification.

We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i,j) = C(i,j). We complement the known EXP-hardness of computing the exact value of a succinct zero-sum game by several results on approximating the value. (1) We prove that approximating the value of a succinct zero-sum game to within an additive error is complete for the class promise- $$S^{p}_{2}$$ , the “promise” version of $$S^{p}_{2}$$ . To the best of our knowledge, it is the first natural problem shown complete for this class. (2) We describe a ZPP NP algorithm for constructing approximately optimal strategies, and hence for approximating the value, of a given succinct zero-sum game. As a corollary, we obtain, in a uniform fashion, several complexity-theoretic results, e.g., a ZPP NP algorithm for learning circuits for SAT (Bshouty et al., JCSS, 1996) and a recent result by Cai (JCSS, 2007) that $$S^{p}_{2} \subseteq$$ ZPP NP . (3) We observe that approximating the value of a succinct zero-sum game to within a multiplicative factor is in PSPACE, and that it cannot be in promise- $$S^{p}_{2}$$ unless the polynomial-time hierarchy collapses. Thus, under a reasonable complexity-theoretic assumption, multiplicative-factor approximation of succinct zero-sum games is strictly harder than additive-error approximation.

We consider the relationship between the complexities of k-SAT and those of SAT restricted to formulas of constant density. Let skbe the infimum of those c ges 0 such that k-SAT on n variables can be decided in time O(2cn) and dDeltabe the infimum of those c ges 0 such that SAT on n variables and les Deltan clauses can be decided in time O(2cn). We show that limkrarrinfinsk= limDeltararrinfindDelta. So, for any epsi > 0, k-SAT can be solved in 2(1-epsi)ntime independent of k if and only if the same is true for SAT with any fixed density of clauses to variables. We derive some interesting consequences from this. For example, assuming that 3-SAT is exponentially hard (that is, s3> 0), SAT of any fixed density can be solved in time whose exponent is strictly less than that for general SAT. We also give an improvement to the sparsification lemma of Impagliazzo et al. (1998) showing that instances of k-SAT of density slightly more than exponential in k are almost the hardest instances of k-SAT. The previous result showed this for densities doubly exponential in k

We consider the problem of approximately locally list-decoding direct product codes. For a parameter k, the k-wise direct product encoding of an N-bit message msg is an Nk-length string over the alphabet {0, l}kindexed by k-tuples (i1, .. ., ik) isin {1,..., N}kso that the symbol at position (i1, .. ., ik) of the codeword is msg(i1)...msg(ik). Such codes arise naturally in the context of hardness amplification of Boolean functions via the direct product lemma (and the closely related Yao 's XOR Lemma), where typically k Lt N (e.g., k = poly log N). We describe an efficient randomized algorithm for approximate local list-decoding of direct product codes. Given access to a word which agrees with the k-wise direct product encoding of some message msg in at least an epsiv fraction of positions, our algorithm outputs a list of poly(l/epsiv) Boolean circuits computing N-bit strings (viewed as truth tables of log N-variable Boolean functions) such that at least one of them agrees with msg in at least 1 - delta fraction of positions, for delta = O(k-0.1), provided that epsiv = Omega(poly(l/k); the running time of the algorithm is polynomial in log N and 1/epsiv. When epsiv > epsivkalphafor a certain constant alpha > 0, we get a randomized approximate list-decoding algorithm that runs in time quasi-polynomial in 1/epsiv (i.e., (1/epsiv)poly log 1epsiv/)By concatenating the k-wise direct product codes with Hadamard codes, we obtain locally list-decodable codes over the binary alphabet, which can be efficiently approximately list-decoded from fewer than frac12 - epsiv fraction of corruptions as long as epsiv = Omega(poly(l/k)). As an immediate application, we get uniform hardness amplification for PNPpar, the class of languages reducible to NP through one round of parallel oracle queries: If there is a language in PNPparthat cannot be decided by any BPP algorithm on more that 1 $1/nOmega(1)fraction of inputs, then there is another language in PNPparthat cannot be decided by any BPP algorithm on more than frac12 + 1/nomega(1)fraction of inputs

Among the most important modern algorithmic techniques is the use of random decisions. Starting in the 1970's, many of the most significant results were randomized algorithms solving basic compuatational problems that had (to that time) resisted efficient deterministic computation. (Ber72, SS79, Rab80, Sch80, Zip79, AKLLR). In contrast, many of the most exciting recent work has been on derandomizing these same algorithms, coming up with efficient deterministic versions, e.g., (AKS02, Rein05). This raises the question, can such results be obtained for all randomized algorithms? Will the remaining classical randomized algorithms be derandomized by similar techniques?Clear but complicated answers to these questions have emerged from complexity-theoretic studies of randomized complexity classes (e.g., RP and BPP) and pseudo-random generators. These questions are inextricably linked to another basic problem in complexity: which functions require large circuits to compute?In this talk, we'll survey some results from the theory of derandomization. I'll stress connections to other questions, especially circuit complexity, explicit extractors, hardness amplification, and error-correcting codes. Much of the talk is based on joint work with Valentine Kabanets and Avi Wigderson, but it will also include results by many other researchers.A priori, possibilities concerning the power of randomized algorithms include:

In this work we give the first deterministic extractors from a constant number of weak sources whose entropy rate is less than 1/2. Specifically, for every $\delta >0$ we give an explicit construction for extracting randomness from a constant (depending polynomially on $1/\delta$) number of distributions over $\bits^n$, each having min‐entropy $\delta n$. These extractors output n bits that are $2^{-n}$ close to uniform. This construction uses several results from additive number theory, and in particular a recent result of Bourgain et al. We also consider the related problem of constructing randomness dispersers. For any constant output length m, our dispersers use a constant number of identical distributions, each with requires min‐entropy $\Omega(\log n)$, and outputs every possible m‐bit string with positive probability. The main tool we use is a variant of the “stepping‐up lemma” of Erdo˝s and Hajnal used in establishing a lower bound on the Ramsey number for hypergraphs.

We show that constant-depth Frege systems with counting axioms modulo m polynomially simulate Nullstellensatz refutations modulo m . Central to this is a new definition of reducibility from propositional formulas to systems of polynomials. Using our definition of reducibility, most previously studied propositional formulas reduce to their polynomial translations. When combined with a previous result of the authors, this establishes the first size separation between Nullstellensatz and polynomial calculus refutations. We also obtain new upper bounds on refutation sizes for certain CNFs in constant-depth Frege with counting axioms systems.

In this work we give the first deterministic extractors from a constant number of weak sources whose entropy rate is less than 1/2. Specifically, for every /spl delta/ > 0 we give an explicit construction for extracting randomness from a constant (depending polynomially on 1//spl delta/) number of distributions over {0, l}n, each having min-entropy /spl delta/n. These extractors output n bits, which are 2/sup -n/ close to uniform. This construction uses several results from additive number theory, and in particular a recent one by Bourgain, Katz and Tao (2003) and of Konyagin (2003). We also consider the related problem of constructing randomness dispersers. For any constant output length m, our dispersers use a constant number of identical distributions, each with min-entropy /spl Omega/(log n) and outputs every possible m-bit string with positive probability. The main tool we use is a variant of the "stepping-up lemma" used in establishing lower bound on the Ramsey number for hyper-graphs (Erdos and Hajnal, 1980).

We prove a new switching lemma that works for restrictions that set only a small fraction of the variables and is applicable to formulas in disjunctive normal form (DNFs) with small terms. We use this to prove lower bounds for the Res(k) propositional proof system, an extension of resolution which works with k-DNFs instead of clauses. We also obtain an exponential separation between depth d circuits of bottom fan-in k and depth d circuits of bottom fan-in k + 1. Our results for Res(k) are as follows:The 2n to n weak pigeonhole principle requires exponential size to refute in Res(k) for $k \leq \sqrt{\log n / \log \log n } $. For each constant k, there exists a constant w > k so that random w-CNFs require exponential size to refute in Res(k). For each constant k, there are sets of clauses which have polynomial size Res(k + 1) refutations but which require exponential size Res(k) refutations.

A fruitful connection between algorithm design and proof complexity is the formalization of the DPLL approach to satisfiability testing in terms of tree-like resolution proofs. We consider extensions of the DPLL approach that add some version of memoization, remembering formulas the algorithm has previously shown unsatisfiable. Various versions of such formula caching algorithms have been suggested for satisfiability and stochastic satisfiability (S. M. Majercik et al., 1998; F. Bacchus et al., 2003). We formalize this method, and characterize the strength of various versions in terms of proof systems. These proof systems seem to be both new and simple, and have a rich structure. We compare their strength to several studied proof systems: tree-like resolution, regular resolution, general resolution, and Res(k). We give both simulations and separations.

We provide some evidence that unique k-SAT is as hard to solve as general k-SAT, where k-SAT denotes the satisfiability problem for k-CNFs and unique k-SAT is the promise version where the given formula has 0 or 1 solutions. Namely, defining for each k/spl ges/1, s/sub k/=inf{/spl delta//spl ges/0|/spl exist/aO(2/sup /spl delta/n/)-time randomized algorithm for k-SAT} and, similarly, /spl sigma//sub k/=inf{/spl delta//spl ges/0|/spl exist/aO(2/sup /spl delta/n/)-time randomized algorithm for Unique k-SAT}, we show that lim/sub k/spl rarr//spl infin//s/sub k/=lim/sub k/spl rarr//spl infin///spl sigma//sub k/. As a corollary, we prove that, if Unique 3-SAT can be solved in time 2/sup /spl epsi/n/ for every /spl epsi/>0, then so can k-SAT for k/spl ges/3. Our main technical result is an isolation lemma for k-CNFs, which shows that a given satisfiable k-CNF can be efficiently probabilistically reduced to a uniquely satisfiable k-CNF, with nontrivial, albeit exponentially small, success probability.

We show that if RP has p-measure nonzero then ZPP=EXP. As corollaries, we obtain a zero-one law for RP, and that both probabilistic classes ZPP and RP have the same p-measure. Finally we prove that if NP has p-measure nonzero then NP=AM.

We define and study strong diagonalization and compare it to weak diagonalization, implicit in the work of D. Kozen (1980). Kozen's result shows that virtually every separation can be recast as weak diagonalization. We show that there are classes of languages, which cannot be separated by strong diagonalization and provide evidence that strong diagonalization does not relativize. We also define two kinds of indirect diagonalization and study their power: Since we define strong diagonalization in terms of universal languages, we study their complexity. We distinguish and compare weak and strict universal languages. Finally we analyze some apparently weaker variants of universal languages, which we call pseudouniversal languages, and show that under weak closure conditions they easily yield universal languages.

We present two logical systems for reasoning about cryptographic constructions which are sound with respect to standard cryptographic definitions of security. Soundness of the first system is proved using techniques from nonstandard models of arithmetic. Soundness of the second system is proved by an interpretation into the first system. We also present examples of how these systems may be used to formally prove the correctness of some elementary cryptographic constructions.

We show that derandomizing Polynomial Identity Testing is, essentially, equivalent to proving circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or, even, nondeterministic subexponential time, infinitely often) whether a given arithmetic circuit over integers computes an identically zero polynomial, then either (i) NEXP ⊄ P/poly or (ii) Permanent is not computable by polynomial-size arithmetic circuits. We also prove a (partial) converse: If Permanent requires superpolynomial-size arithmetic circuits, then one can test in subexponential time whether a given arithmetic formula computes an identically zero polynomial.Since Polynomial Identity Testing is a coRP problem, we obtain the following corollary: If RP=P (or, even, coRP⊆ ∩ε > 0NTIME(2(nε)), infinitely often), then NEXP is not computable by polynomial-size arithmetic circuits. Thus, establishing that RP=coRP or BPP=P would require proving superpolynomial lower bounds for Boolean or arithmetic circuits. We also show that any derandomization of RNC would yield new circuit lower bounds for a language in NEXP.

We prove a new switching lemma that works for restrictions that set only a small fraction of the variables and is applicable to DNFs with small conjunctions. We use this to prove lower bounds for the Res(k) propositional proof system, an extension of resolution which works with k-DNFs instead of clauses. We also obtain an exponential separation between depth d circuits of bottom fan-in k and depth d circuits of bottom fan-in k+1. Our results for Res(k) are: 1. The 2n to n weak pigeonhole principle requires exponential size to refute in Res(k), for k /spl les/ /spl radic/(log n/ log log n). 2. For each constant k, there exists a constant w > k so that random w-CNFs require exponential size to refute in Res(k). 3. For each constant k, there are sets of clauses which have polynomial size Res(k+1) refutations, but which require exponential size Res(k) refutations.

We consider the problem of providing a resolution proof of the statement that a given graph with n vertices and /spl Delta/n edges does not contain an independent set of size k. For randomly chosen graphs with constant /spl Delta/, we show that such proofs almost surely require size exponential in n. Further, for /spl Delta/=o(n/sup 1/5/) and any k/spl les/n/5, we show that these proofs almost surely require size 2(n/sup /spl delta//) for some global constant /spl delta/>0, even though the largest independent set in graphs with /spl Delta//spl ap/n/sup 1/5/ is much smaller than n/5. Our result shows that almost all instances of the independent set problem are hard for resolution. It also provides a lower bound on the running time of a certain class of search algorithms for finding a largest independent set in a given graph.

Restricting the search space {0, 1}/sup n/ to the set of truth tables of "easy" Boolean functions on log n variables, as well as using some known hardness-randomness tradeoffs, we establish a number of results relating the complexity of exponential-time and probabilistic polynomial-time complexity classes. In particular, we show that NEXP/spl sub/P/poly/spl hArr/NEXP=MA; this can be interpreted to say that no derandomization of MA (and, hence, of promise-BPP) is possible unless NEXP contains a hard Boolean function. We also prove several downward closure results for ZPP, RP, BPP, and MA; e.g., we show EXP=BPP/spl hArr/EE=BPE, where EE is the double-exponential time class and BPE is the exponential-time analogue of BPP.

We give a family of tautologies whose algebraic translations have constant-degree, polynomial size polynomial calculus refutations over Z/sub 2/, but which require superpolynomial size bounded-depth Frege proofs from Count/sub 2/ axioms. This gives a superpolynomial size separation of bounded-depth Frege plus mod 2 counting axioms from bounded-depth Frege plus parity gates. Combined with another result of the authors, it gives the first size (as opposed to degree) separation between the polynomial calculus and Nullstellensatz systems.

We give the first construction of a pseudo-random generator with optimal seed length that uses (essentially) arbitrary hardness.It builds on the novel recursive use of the NWgenerator in [8], which produced many optimal generators one of which was pseudo-random.This is achieved in two stages -first significantly reducing the number of candidate generators, and then efficiently combining them into one.We also give the first construction of an extractor with optimal seed length, that can handle sub-polynomial entropy levels.It builds on the fundamental connection between extractors and pseudo-random generators discovered by Trevisan [21], combined with construction above.Moreover, using Kolmogorov Complexity rather than circuit size in the analysis gives super-polynomial savings for our construction, and renders our extractors better than known for all entropy levels.

Two important algebraic proof systems are the Nullstellensatz system and the polynomial calculus (also called the Grobner system). The Nullstellensatz system is a propositional proof system based on Hilbert's Nullstellensatz, and the polynomial calculus (PC) is a proof system which allows derivations of polynomials, over some field. The complexity of a proof in these systems is measured in terms of the degree of the polynomials used in the proof. The mod p counting principle can be formulated as a set MOD/sub p//sup n/ of constant-degree polynomials expressing the negation of the counting principle. The Tseitin mod p principles, TS/sub n/(p), are translations of the MOD/sub p//sup n/ into the Fourier basis. The present paper gives linear lower bounds on the degree of polynomial calculus refutations of MOD/sub p//sup n/ over p fields of characteristic q /spl ne/ p and over rings Z/sub q/ with q,p relatively prime. These are the first linear lower bounds for the polynomial calculus. As it is well-known to be easy to give constant degree polynomial calculus (and even Nullstellensatz) refutations of the MOD/sub p//sup n/ polynomials over F/sub p/, our results imply that the MOD/sub p//sup n/ polynomials have a linear gap between proof complexity for the polynomial calculus over F/sub p/ and over F/sub q/. We also obtain a linear gap for the polynomial calculus over rings Z/sub p/ and Z/sub q/ where p, q do not have identical prime factors.

The problem of k-SAT is to determine if the given k-CNF has a satisfying solution. It is a celebrated open question as to whether it requires exponential time to solve k-SAT for k/spl ges/3. Define s/sub k/ (for k/spl ges/3) to be the infimum of {/spl delta/: there exists an O(2/sup /spl delta/n/) algorithm for solving k-SAT}. Define ETH (Exponential-Time Hypothesis) for k-SAT as follows: for k/spl ges/3, s/sub k/>0. In other words, for k/spl ges/3, k-SA does not have a subexponential-time algorithm. In this paper we show that s/sub k/ is an increasing sequence assuming ETH for k-SAT: Let s/sub /spl infin// be the limit of s/sub k/. We in fact show that s/sub k//spl les/(1-d/k) s/sub /spl infin// for some constant d>0.

We show a general reduction that derives lower bounds on degrees of polynomial calculus proofs of tautologies, over any field of characteristic (other than 2) from lower bounds for resolution proofs of a related set of linear equations module 2. We apply this to derive linear lower bounds on the degrees of PC proofs of randomly generated tautologies.

Various efforts have been made to derandomize probabilistic algorithms using the assumption that there exists a problem in E=dtime(2/sup O(n)/) that requires circuits of size s(n) (for some function s). These results are based on the NW (Nisan & Wigderson, 1997) generator. For the strong lower bound s(n)=2/sup ϵn/, the optimal derandomization is P=BPP. However, for weaker lower bound functions s(n), these constructions fall short of the natural conjecture for optimal derandomization that bptime(t)⊆ dtime(2O[s/sup -1/(t)]). The gap is due to an inherent efficiency limitation in NW-style pseudorandom generators. We are able to obtain derandomization in almost optimal time using any lower bound s(n). We do this by using the NW-generator in a more sophisticated way. We view any failure of the generator as a reduction from the given hard function to its restrictions on smaller input sizes. Thus, either the original construction works optimally or one of the restricted functions is as hard as the original. Any such restriction can then be plugged into the NW-generator recursively. This process generates many candidate generators, and at least one is guaranteed to be good. To perform the approximation of the acceptance probability of the given circuit, we run a tournament between the candidate generators which yields an accurate estimate. We explore information theoretic analogs of our new construction. The inherent limitation of the NW-generator makes the extra randomness required by that extractor suboptimal. However, applying our construction, we get an almost optimal disperser.

This paper gives nearly optimal lower bounds on the minimum degree of polynomial calculus refutations of Tseitin's graph tautologies and the mod p counting principles, p >_ 2. The lower bounds apply to the polynomial calculus over fields or rings.These are the first linear lower bounds for polynomial calculus; moreover, they distinguish linearly between proofs over fields of characteristic p and T, y # r, and more generally distinguish linearly the rings Z, and Z, where 4 and P do not have the identical prime factors.

Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any one-way function. Since it is easy to construct a one-way function from a pseudorandom generator, this result shows that there is a pseudorandom generator if and only if there is a one-way function.

We investigate the relationship between interactive proofs of membership and interactive proofs of knowledge. Previous results in this area show that many proofs of membership for some languages are also proofs of knowledge of an associated relation, raising the question of whether all proofs of membership are proofs of knowledge. In this paper we clarify the relationship between these two notions of proofs. It turns out that a precise relationship depends on the kind of relation considered. Clearly, any proof of membership is a proof of knowledge for some easy to compute relation. On the other hand, we define a notion of tight relations, referring to relations that capture the computational advantage communicated by a prover to a poly-time verifier in an interactive protocol.

For several NP-complete problems, there have been a progression of better but still exponential algorithms. In this paper, we address the relative likelihood of sub-exponential algorithms for these problems. We introduce a generalized reduction which we call Sub-Exponential Reduction Family (SERF) that preserves sub-exponential complexity. We show that CircuitSAT is SERF-complete for all NP-search problems, and that for any fixed k, k-SAT, k-Colorability, k-Set Cover, Independent Set, Clique, Vertex Cover, are SERF--complete for the class SNP of search problems expressible by second order existential formulas whose first order part is universal. In particular, sub-exponential complexity for any one of the above problems implies the same for all others. We also look at the issue of proving strongly exponential lower bounds for AC 0 ; that is, bounds of the form 2 \\Omega\\Gamma n) . This problem is even open for depth-3 circuits. In fact, such a bound for depth-3 circuits with even l...

We prove that if BPP/spl ne/EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input (on every samplable ensemble for infinitely many input sizes). This is the first derandomization result for BPP based on uniform, noncryptographic hardness assumptions. It implies the following gap in the average-instance complexities of problems in BPP: either these complexities are always sub-exponential or they contain arbitrarily large exponential functions. We use a construction of a small "pseudorandom" set of strings from a "hard function" in EXP which is identical to that used in the analogous non-uniform results described previously. However, previous proofs of correctness assume the "hard function" is not in P/poly. They give a non-constructive argument that a circuit distinguishing the pseudo-random strings from truly random strings implies that a similarly-sized circuit exists computing the "hard function". Our main technical contribution is to show that, if the "hard function" has certain properties, then this argument can be made constructive. We then show that, assuming ESP/spl sube/P/poly, there are EXP-complete functions with these properties.

Whether or not parallel repetition lowers the error has been a fundamental question in the theory of protocols, with applications in many different areas. It is well known that parallel repetition reduces the error at an exponential rate in interactive proofs and Arthur-Merlin games. It seems to have been taken for granted that the same is true in arguments, or other proofs where the soundness only holds with respect to computationally bounded parties. We show that this is not the case. Surprisingly, parallel repetition can actually fail in this setting. We present four-round protocols whose error does not decrease under parallel repetition. This holds for any (polynomial) number of repetitions. These protocols exploit non-malleable encryption and can be based on any trapdoor permutation. On the other hand we show that for three-round protocols the error does go down exponentially fast. The question of parallel error reduction is particularly important when the protocol is used in cryptographic settings like identification, and the error represents the probability that an intruder succeeds.

We prove that the Berman-Hartmanis isomorphism conjecturers true under ACO reductions.More generafly, we show three theorems that hold for any comdexitv class C closed under (uniform) TCO-commtable man~-one" reductions.Isomorp'hism:The sets c~mplete for Cunder ACO reductions are afl isomorphic under isomorphisms computable and invertible by ACO circuits of depth three.Ga : p The sets that are complete for C under ACO and NC reducibility coincide.Stop Gap: The sets that are complete for C under ACO[mod 2] and ACO reducibility do not coincide.(These theorems hold both in the non-uniform and P-uniform settings.) To prove the second theorem for P-uniform settings, we show how to derandomize a version of the switching lemma, which may be of independent interest.(We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.)

The following size--depth tradeoff for threshold circuits is obtained: any threshold circuit of depth d that computes the parity function on n variables must have at least $n^{1 + c\theta^{-d }}$ edges, where $c>0$ and $\theta \leq 3$ are constants independent of n and d. Previously known constructions show that up to the choice of c and $\theta$ this bound is best possible. In particular, the lower bound implies an affirmative answer to the conjecture of Paturi and Saks that a bounded-depth threshold circuit that computes parity requires a superlinear number of edges. This is the first superlinear lower bound for an explicit function that holds for any fixed depth and the first that applies to threshold circuits with unrestricted weights. The tradeoff is obtained as a consequence of a general restriction theorem for threshold circuits with a small number of edges: For any threshold circuit with n inputs, depth d, and at most $kn$ edges, there exists a partial assignmentto the inputs that fixes the output of the circuit to a constant while leaving $\lfloor n/(c_1k)^{c_2\theta^{d}} \rfloor$ variables unfixed, where $c_1,c_2 > 0$ and $ \theta \leq 3$ are constants independent of n, k, and d. A tradeoff between the number of gates and depth is also proved: any threshold circuit of depth d that computes the parity of n variables has at least $(n/2)^{1/2(d-1)}$ gates. This tradeoff, which is essentially the best possible, was proved previously (with a better constant in the exponent) for the case of threshold circuits with polynomially bounded weights in [K. Siu, V. Roychowdury, and T. Kailath, IEEE Trans. Inform. Theory, 40 (1994), pp. 455--466]; the result in the present paper holds for unrestricted weights.

The proof of Wagner's conjecture by Robertson and Seymour gives a finite description of any family of graphs which is closed under the minor ordering. This description is a finite set of minimal graphs not in the family; these graphs are called the obstructions of the family. Since the intersection and union of two minor closed graph families is again a minor closed graph family, an interesting question regards computing the obstructions of the new family given the obstructions for the original two families. It is easy to compute the obstructions of the intersection, but nontrivial to compute those of the union. In this paper, we show that if the original families are planar then the planar obstructions of the union are no larger than nO(n2), where n is the size of the largest obstruction of the original families.

A propositionalproof system can be viewed as a non-deterministic algorithm for the (co-NP complete) unsatisfiabilit y problem.Many such proof systems, such as resolution, are rdso used as the basis for heuristics which deterministicrdly search for short proofs in the system.We discuss a propositional proof system baaed on algebraic rea soning, which we call the Groebner proof system because of a tight connection to the Groebner basis algorithm.For an appropriate measure of proof size, we show that (a degree-limited implement =ation of ) the Groebner basis algorithm finds a Groebner proof of a tautology in time polynomial in the size of the smallest such proof, In other words, urdike most proof systems, the non-deterministic algorithm can be converted to a deterministic one without loss in power.We then compare the power of the Groebner proof system to more studied systems.We show that the Groebner system polynomially simulates Horn clause resolution, quasi-polynomially simulates tree-like resolution, and weakly exponentially simulates resolution.Thus, Groebnerproofs will have better than worst-case behaviour on the same classes of inputs that resolution does.On the other hand, there are simple tautologies which have polynomialsize Groebner proofs but which require exponential-size resolution proofs.We also compare the Groebner proof system to the similar Nullstellensatz proof system introduced in [BIK+94].We show a family of tautologies that have degree 3 (and hence polynomirdsize) Groebner refutations, but which require @(W degree Nullst ellensat z refutations.Thus, there is an exponential separation between the two systems.These results suggest that the Groebner basis algorithm might replace mmlutian M s bseie far hem.ieticsfar NP.emnple&e pmh

We introduce a variant of Aldous and Vazirani's "Go with the winners" algorithm that can be used for search graphs that are not trees.We analyze the algorithm in terms of the properties of a tree-decomposition of the search graph.We show a large clazs of distributions for search graphs so that "Go with the winners" works well with high probability y for almost all graphs from the distribution.We also give a sufficient combinatorial property that ensures good performance.

We consider the problem of determining, given a graph G and specified nodes s and t, whether or not there is a path of at most k edges in G from s to t. We show that solving this problem on polynomial-size unbounded fan-in circuits, requires depth /spl Omega/(loglogk), improving on a depth lower bound of n(log*k) when k=log/sup O(1/) n. In addition we show that there is a constant c such that for k/spl les/logn, any depth d unbounded fan-in circuit for this problem requires size at least n/sup ck/spl epsiv/d/ where /spl epsiv//sub d/=/spl phi//sup -2d//3 and /spl phi/ is the golden mean. This latter result improves on an n/sup /spl Omega/(log(d+3/k)) bound where log/sup (i/) is the i-fold composition of log with itself. The key to our technique is a new form of switching lemma which combines some of the features of iteratively shortening terms due to Furst, Saxe, and Sipser (1981) and Ajtai (1983) with the kinds of switching lemma arguments introduced by Yao (1985), Hastad (1986), and Cai (1986) that have been the methods of choice for subsequent results.

Consider a decision problem that cannot be 1-/spl delta/ approximated by circuits of a given size in the sense that any such circuit fails to give the correct answer on at least a /spl delta/ fraction of instances. We show that for any such problem there is a specific "hard core" set of inputs which is at least a /spl delta/ fraction of all inputs and on which no circuit of a slightly smaller size can get even a small advantage over a random guess. More generally, our argument holds for any non uniform model of computation closed under majorities. We apply this result to get a new proof of the Yao XOR lemma (A.C. Yao, 1982), and to get a related XOR lemma for inputs that are only k wise independent.

Papadimitriou introduced several classes of NP search problems based on combinatorial principles which guarantee the existence of solutions to the problems.Many interesting search problems not known to be solvable in polynomial time are contained in these classes, and a number of them are complete problems.We consider the question of the relative complexity of these search problem classes.We prove several separations which show that in a generic relativized world, the search classes are distinct and there is a standard search problem in each of them that is not computationally equivalent to any decision problem.(Naturally, absolute separations would imply that P 6 = NP.)Our separation proofs have interesting combinatorial content and go to the heart of the combinatorial principles on which the classes are based.We derive one result via new lower bounds on the degrees of polynomials asserted to exist by Hilbert's Nullstellensatz over nite elds.

The weak form of the Hilbert's Nullstellensatz says that a system of algebraic equations over a field, Q/sub i/(x~)=0, does not have a solution in the algebraic closure iff 1 is in the ideal generated by the polynomials Q/sub i/(x~). We shall prove a lower bound on the degrees of polynomials P/sub i/(x~) such that /spl Sigma//sub i/ P/sub i/(x~)Q/sub i/(x~)=1. This result has the following application. The modular counting principle states that no finite set whose cardinality is not divisible by q can be partitioned into q-element classes. For each fixed cardinality N, this principle can be expressed as a propositional formula Count/sub q//sup N/. Ajtai (1988) proved recently that, whenever p, q are two different primes, the propositional formulas Count/sub q//sup qn+1/ do not have polynomial size, constant-depth Frege proofs from instances of Count/sub p//sup m/, m/spl ne/0 (mod p). We give a new proof of this theorem based on the lower bound for the Hilbert's Nullstellensatz. Furthermore our technique enables us to extend the independence results for counting principles to composite numbers p and q. This results in an exact characterization of when Count/sub q/ can be proven efficiently from Count/sub p/, for all p and q.>

We study the complexity of cutting planes (CP) refutations, and tree-like CP refutations. Tree-like CP proofs are natural and still quite powerful. In particular, the propositional pigeonhole principle (PHP) has been shown to have polynomial-sized tree-like CP proofs. Our main result shows that a family of tautologies, introduced in this paper requires exponential-sized tree-like CP proofs. We obtain this result by introducing a new method which relates the size of a CP refutation to the communication complexity of a related search problem. Because these tautologies have polynomial-sized Frege proofs, it follows that tree-like CP cannot polynomially simulate Frege systems.>

We define pseudorandom generators for Yao's twoparty communication complexity model and exhibit a simple construction, based on expanders, for it.We then use a recursive composition of such generators to obtain pseudorandom generators that fool distributed network algorithms.While the construction and the proofs are simple, we demonstrate the generality of such generators by giving several applications.1 a pseudorandom generator, which is said to fool the

Article Size-depth trade-offs for threshold circuits Share on Authors: Russell Impagliazzo View Profile , Ramamohan Paturi View Profile , Michael E. Saks View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 541–550https://doi.org/10.1145/167088.167233Online:01 June 1993Publication History 3citation293DownloadsMetricsTotal Citations3Total Downloads293Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP).We also obtain an ~(log log rz)depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle.Our theorem nearly completes the search for the exact complexity of the PHP, as Sam Buss has constructed polynomial-size, log ndepth Frege proofs for the PHP.The main lemma in our proof can be viewed as a general H&.stad-style Switching Lemma for restrictions that are partial matchings.Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.

M. Karchmer et al. (1991) considered the circuit depth complexity of n-bit Boolean function constructed by composing up to d=log n/log log n levels of k=log-n-bit Boolean functions. Any such function is in AC/sup 1/. They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires dk in Omega (log/sup 2/ n/log log n) depth. This would separate AC/sup 1/ from NC/sup 1/. They recommend using the communication game characterization of circuit depth. They suggest an intermediate problem which they call the universal composition relation. An almost optimal lower bound of dk-O(d/sup 2/(k log k)/sup 1/2/) is given for this problem. In addition, a proof, directly in terms of communication complexity, that there is a function on k bits requiring Omega (k) circuit depth is presented.>

The proof of Wagner's conjecture by N. Robertson and P. Seymour gives a finite description of any family of graphs which is closed under the minor ordering, called the obstructions of the family. Since the intersection and the union of two minor closed graph families are again a minor closed graph family, an interesting question is that of computing the obstructions of the new family given the obstructions for the original two families. It is easy to compute the obstructions of the intersection, but, until very recently, it was an open problem to compute the obstructions of the union. It is shown that if the original families are planar, then the obstructions of the union are no larger than n to the O(n/sup 2/) power, where n is the size of the largest obstruction of the original family.>

The task of transforming a weak one-way function (which may be easily inverted on all but a polynomial fraction of the range) into a strong one-way function (which can be easily inverted only on a negligible function of the range) is considered. The previously known transformation does not preserve the security (i.e. the running time of the inverting algorithm) within any polynomial. Its resulting function, F(x), applies the weak one-way function to many small (of length mod x mod /sup theta /, theta>

Distributed NP (DNP) problems are ones supplied with probability distributions of instances. It is shown that every DNP problem complete for P-time computable distributions is also complete for all distributions that can be sampled. This result makes the concept of average-case NP completeness robust and the question of the average-case complexity of complete DNP problems a natural alternative to P=?NP. Similar techniques yield a connection between cryptography and learning theory.

It is shown that many of the standard cryptographic tasks are equivalent to the usual definition of a one-way function. In particular, it is shown that for some of the standard cryptographic tasks any secure protocol for the task can be converted into a one-way function in the usual sense, and thus the security of any proposed protocol for these tasks is implicitly based on a function being 'one-way.' Thus, the usual definition of a one-way function is robust; any one-way function with respect to another definition on which a secure cryptographic protocol can be based can be used to construct a one-way function in the usual sense. The authors focus on private-key encryption, identification/authentication, bit commitment, and coin flipping by telephone. However, the proof techniques presented here can be easily adopted to prove analogous results for other cryptographic tasks.>

Very efficient constructions, based on the intractability of the subset sum problem for certain dimensions, are shown for a pseudorandom generator and for a universal one-way hash function. (Pseudorandom generators can be used for private key encryption, and universal one-way hash functions for signature schemes). The increase in efficiency in the construction is due to the fact that many bits can be generated/hashed with one application of the assumed one-way function. All the constructions can be implemented in NC using an optimal number of processors.>

The following propositions are considered: (1) E=NE (i.e. it is decidable in exponential time whether there is a solution for an exponential-type search problem). (2) Every exponential-type search problem is solvable in exponential time. (3) The first solution to every exponential-type search problem can be found in exponential time. (4) E=E/sup NP/. It is easy to see that (4) implies (3) implies (2) implies (1). It has been conjectured that the first and last of these assumptions are equivalent in every relativized world. It is proved here that there exist relativized words in which the last two implications are not reversible. This is evidence that the search problem is not reducible to decision problems in exponential time. It is also proved that the third and fourth assumptions are equivalent. The combinatorial core of the separation results is a lower bound on the parallel complexity of a generalized version of the X-search problem.>

It is shown that modified versions of the linear congruential generator and the shift register generator are provably good for amplifying the correctness of a probabilistic algorithm. More precisely, if r random bits are needed for a BPP algorithm to be correct with probability at least 2/3, then O(r+k/sup 2/) bits are needed to improve this probability to 1-2/sup -k/. A different pseudorandom generator that is optimal, up to a constant factor, in this regard is also presented. It uses only O(r+k) bits to improve the probability to 1-2/sup -k/. This generator is based on random walks on expanders. The results do not depend on any unproven assumptions. It is shown that the modified versions of the shift register and linear congruential generators can be used to sample from distributions using, in the limit, the information-theoretic lower bound on random bits.>

We show that the existence of one-way functions is necessary and sufficient for the existence of pseudo-random generators in the following sense. Let ƒ be an easily computable function such that when x is chosen randomly: (1) from ƒ(x) it is hard to recover an x1 with ƒ(x1) = ƒ(x) by a small circuit, or; (2) ƒ has small degeneracy and from ƒ(x) it is hard to recover x by a fast algorithm. From one-way functions of type (1) or (2) we show how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa. Previous results show how to construct pseudo-random generators from one-way functions that have special properties ([Blum, Micali 82], [Yao 82], [Levin 85], [Goldreich, Krawczyk, Luby 88]).

We present strong evidence that the implication, “if one-way permutations exist, then secure secret key agreement is possible”, is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. We consider a world where all parties have access to a black box for a randomly selected permutation. Being totally random, this permutation will be strongly one-way in a provable, information-theoretic way. We show that, if P = N P, no protocol for secret key agreement is secure in such a setting. Thus, to prove that a secret key agreement protocol which uses a one-way permutation as a black box is secure is as hard as proving P ≠ N P. We also obtain, as a corollary, that there is an oracle relative to which the implication is false, i.e., there is a one-way permutation, yet secret-exchange is impossible. Thus, no technique which relativizes can prove that secret exchange can be based on any one-way permutation. Our results present a general framework for proving statements of the form, “Cryptographic application X is not likely possible based solely on complexity assumption Y.”

In this paper, we examine various complexity issues relative to an oracle for a generic set in order to determine which are the more "natural" conjectures for these issues. Generic oracle results should be viewed as parallels to random oracle results, as in [BG]; the two are in many ways related, but, as we shall exhibit, not equivalent. Looking at computation relative to a generic oracle is in some ways a better reflection of computation without an oracle; for example, whereas adding a random oracle allows a deterministic polynomial-time machine to solve any problem in BPP, adding a generic oracle will not help solve any recursive problem faster than it could be solved without an oracle. Generic sets were first introduced by Cohen as a tool for proving independence results in set theory [Co]. Their recursion theoretic properties have also been explored in depth; for example, see [J] and [Ku2]. Some related work using forcing and/or generic sets as tools in oracle constructions can be found in [Ku3], [Do], [P], and [A-SFH]. However, this is to our knowledge the first knowledge the first thorough examination of complexity relative to a generic Oracle.