Time-bounded conditional Kolmogorov complexity of a string x given y, Kt(x∣ y), is the length of a shortest program that, given y, prints x within t steps. The Chain Rule for conditional Kt with error e is the following hypothesis: there is a constant c such that, for any strings y,x1,…,xℓ∈{0,1}*, for any ℓ∈ℕ, and all sufficiently large time bounds t,

We investigate randomized LEARN-uniformity, which captures the power of randomness and equivalence queries (EQ) in the construction of Boolean circuits for an explicit problem. This is an intermediate notion between P-uniformity and non-uniformity motivated by connections to learning, complexity, and logic. Building on a number of techniques, we establish the first unconditional lower bounds against LEARN-uniform circuits: –For all$c\geq 1$, there is$L\in \mathsf{P}$that is not computable by circuits of size$n\cdot(\log n)^{c}$generated in deterministic polynomial time with$o(\log n/\log\log n)$equivalence queries to$L$. In other words, small circuits for$L$cannot be efficiently learned using a bounded number of EQs. –For each$k\geq 1$, there is$L\in \mathsf{NP}$such that circuits for$L$of size$O(n^{k})$cannot be learned in deterministic polynomial time with access to$n^{o(1)}$EQs. –For each$k\geq 1$, there is a problem in promise-ZPP that is not in FZPP-uniform$\mathsf{SIZE}[n^{k}]$. –Conditional and unconditional lower bounds against LEARN-uniform circuits in the general setting with randomized uniformity and access to EQs. In all these lower bounds, the learning algorithm may run in arbitrary polynomial time, while the hard problem is computed in some fixed polynomial time. We employ these results to investigate the (un)provability of non-uniform circuit upper bounds (e.g., Is N P contained in$\mathsf{SIZE}[n^{3}]?)$in theories of bounded arithmetic. Some questions of this form have been addressed in recent papers of Krajíček-Oliveira (2017), Müller-Bydzovsky (2020), and Bydzovsky-Krajíček-Oliveira (2020) via a mixture of techniques from proof theory, complexity theory, and model theory. In contrast, by extracting computational information from proofs via a direct translation to LEARN-uniformity, we establish robust unprovability theorems that unify, simplify, and extend nearly all previous results. In addition, our lower bounds against randomized LEARN-uniformity yield unprovability results for theories augmented with the dual weak pigeonhole principle, such as APC1(Jeřábek, 2007), which is known to formalize a large fragment of modern complexity theory. Finally, we make precise potential limitations of theories of bounded arithmetic such as PV (Cook, 1975) and Jeřábek's theory APC1, by showing unconditionally that these theories cannot prove statements like “$\mathsf{NP}\not\subseteq \mathsf{BPP}\wedge \mathsf{NP}\subset \mathsf{io}-\mathsf{P}/\mathsf{poly}$”, i.e., that N P is uniformly “hard” but non-uniformly “easy” on infinitely many input lengths. In other words, if we live in such a complexity world, then this cannot be established feasibly.

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.

The class 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[s]∘𝒢 consists of Boolean functions computable by size-s de Morgan formulas whose leaves are any Boolean functions from a class 𝒢. We give lower bounds and (SAT, Learning, and PRG) algorithms for FORMULA[n^{1.99}]∘𝒢, for classes 𝒢 of functions with low communication complexity. Let R^(k)(𝒢) be the maximum k-party number-on-forehead randomized communication complexity of a function in 𝒢. Among other results, we show that: - The Generalized Inner Product function 𝖦𝖨𝖯^k_n cannot be computed in 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[s]∘𝒢 on more than 1/2+ε fraction of inputs for s = o(n²/{(k⋅4^k⋅R^(k)(𝒢)⋅log (n/ε)⋅log(1/ε))²}). This significantly extends the lower bounds against bipartite formulas obtained by [Avishay Tal, 2017]. As a corollary, we get an average-case lower bound for 𝖦𝖨𝖯^k_n against 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^{1.99}]∘𝖯𝖳𝖥^{k-1}, i.e., sub-quadratic-size de Morgan formulas with degree-(k-1) PTF (polynomial threshold function) gates at the bottom. - There is a PRG of seed length n/2 + O(√s⋅R^(2)(𝒢)⋅log(s/ε)⋅log(1/ε)) that ε-fools FORMULA[s]∘𝒢. For the special case of FORMULA[s]∘𝖫𝖳𝖥, i.e., size-s formulas with LTF (linear threshold function) gates at the bottom, we get the better seed length O(n^{1/2}⋅s^{1/4}⋅log(n)⋅log(n/ε)). In particular, this provides the first non-trivial PRG (with seed length o(n)) for intersections of n half-spaces in the regime where ε ≤ 1/n, complementing a recent result of [Ryan O'Donnell et al., 2019]. - There exists a randomized 2^{n-t}-time #SAT algorithm for 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[s]∘𝒢, where t = Ω(n/{√s⋅log²(s)⋅R^(2)(𝒢)})^{1/2}. In particular, this implies a nontrivial #SAT algorithm for 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^1.99]∘𝖫𝖳𝖥. - The Minimum Circuit Size Problem is not in 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^1.99]∘𝖷𝖮𝖱; thereby making progress on hardness magnification, in connection with results from [Igor Carboni Oliveira et al., 2019; Lijie Chen et al., 2019]. On the algorithmic side, we show that the concept class 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^1.99]∘𝖷𝖮𝖱 can be PAC-learned in time 2^O(n/log n).

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [44], and show that this analysis can be formalized in the bounded arithmetic system VNC1 (corresponding to the “NC1 reasoning”). As a corollary, we prove the assumption made by Jeřábek [28] that a construction of certain bipartite expander graphs can be formalized in VNC1. This in turn implies that every proof in Gentzen's sequent calculus LK of a monotone sequent can be simulated in the monotone version of LK (MLK) with only polynomial blowup in proof size, strengthening the quasipolynomial simulation result of Atserias, Galesi, and Pudlák [9].

This special section comprises nine fully refereed papers whose extended abstracts were presented at the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017) in Berkeley, California, on October 15--17, 2017. The preliminary conference versions of these papers were published by in the FOCS 2017 proceedings. The regular conference program consisted of 90 papers chosen from among 323 submissions. They were selected by a program committee consisting of Aditya Bhaskara, Andrej Bogdanov, Vladimir Braverman, Shiri Chechik, Gil Cohen, Anindya De, Ankit Garg, Josh Grochow, Sean Hallgren, Valentine Kabanets, Gillat Kol, Ravi Kumar, Chris Peikert, Sofya Raskhodnikova, Rahul Santhanam, Yaron Singer, Chaitanya Swamy, Amnon Ta-Shma, Chris Umans (chair), Vinod Vaikuntanathan, Emanuele Viola, Omri Weinstein, and Amir Yehudayoff. The papers invited to this special section were also chosen with the input of the program committee. The nine papers in this section span a broad range of topics, including cryptography, approximation algorithms, hardness of approximation, complexity theory, communication complexity, graph sparsification, and error-correcting codes. Each paper underwent an extensive refereeing process. We thank the authors and the anonymous referees for their efforts. In addition, we would like to thank SICOMP Editors-in-Chief Leonard Schulman and Robert Krauthgamer and SIAM Senior Publications Coordinator Heather Blythe for their help in preparing this special section.

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function f can be computed by a Boolean circuit of size at most theta, for a given parameter theta. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a PRG is called local if its output bit strings, when viewed as the truth table of a Boolean function, can be computed by a Boolean circuit of small size. We get new and improved lower bounds for MCSP that almost match the best-known lower bounds against several circuit models. Specifically, we show that computing MCSP, on functions with a truth table of length N, requires - N^{3-o(1)}-size de Morgan formulas, improving the recent N^{2-o(1)} lower bound by Hirahara and Santhanam (CCC, 2017), - N^{2-o(1)}-size formulas over an arbitrary basis or general branching programs (no non-trivial lower bound was known for MCSP against these models), and - 2^{Omega (N^{1/(d+2.01)})}-size depth-d AC^0 circuits, improving the superpolynomial lower bound by Allender et al. (SICOMP, 2006). The AC^0 lower bound stated above matches the best-known AC^0 lower bound (for PARITY) up to a small additive constant in the depth. Also, for the special case of depth-2 circuits (i.e., CNFs or DNFs), we get an almost optimal lower bound of 2^{N^{1-o(1)}} for MCSP.

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.

A polynomial threshold function (PTF) is defined as the sign of a polynomial p : {0,1}^n ->R. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth. - Satisfiability (#SAT). We give the first zero-error randomized algorithm faster than exhaustive search that counts the number of satisfying assignments of a given constant-depth circuit with a super-linear number of wires whose gates are s-sparse PTFs, for s almost quadratic in the input size of the circuit; here a PTF is called s-sparse if its underlying polynomial has at most s monomials. More specifically, we show that, for any large enough constant c, given a depth-d circuit with (n^{2-1/c})-sparse PTF gates that has at most n^{1+epsilon_d} wires, where epsilon_d depends only on c and d, the number of satisfying assignments of the circuit can be computed in randomized time 2^{n-n^{epsilon_d}} with zero error. This generalizes the result by Chen, Santhanam and Srinivasan (CCC, 2016) who gave a SAT algorithm for constant-depth circuits of super-linear wire complexity with linear threshold function (LTF) gates only. - Quantified derandomization. The quantified derandomization problem, introduced by Goldreich and Wigderson (STOC, 2014), asks to compute the majority value of a given Boolean circuit, under the promise that the minority-value inputs to the circuit are very few. We give a quantified derandomization algorithm for constant-depth PTF circuits with a super-linear number of wires that runs in quasi-polynomial time. More specifically, we show that for any sufficiently large constant c, there is an algorithm that, given a degree-Delta PTF circuit C of depth d with n^{1+1/c^d} wires such that C has at most 2^{n^{1-1/c}} minority-value inputs, runs in quasi-polynomial time exp ((log n)^{O (Delta^2)}) and determines the majority value of C. (We obtain a similar quantified derandomization result for PTF circuits with n^{Delta}-sparse PTF gates.) This extends the recent result of Tell (STOC, 2018) for constant-depth LTF circuits of super-linear wire complexity. - Pseudorandom generators. We show how the classical Nisan-Wigderson (NW) generator (JCSS, 1994) yields a nontrivial pseudorandom generator for PTF circuits (of unrestricted depth) with sub-linearly many gates. As a corollary, we get a PRG for degree-Delta PTFs with the seed length exp (sqrt{Delta * log n})* log^2(1/epsilon).

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 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.

A polynomial threshold function (PTF) of degree d is a boolean function of the form f=sgn(p), where p is a degree-d polynomial, and sgn is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is not close to a constant function, where a boolean function g is called δ-close to constant if, for some vε{1,-1}, we have g(x)=v for all but at most δ fraction of inputs. We show for every PTF f of degree d≥ 1, and parameters 0<δ, r≤ 1/16, that

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 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 consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP^QBF is known to be complete for PSPACE under ZPP reductions. We show that it is not complete under logspace reductions, and indeed it is not even hard for TC under uniform AC^0 reductions. We obtain a variety of consequences that follow if oracle versions of MCSP are hard for various complexity classes under different types of reductions. We also prove analogous results for the problem of determining the resource-bounded Kolmogorov complexity of strings, for certain types of Kolmogorov complexity measures.

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for “easy” Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an n-variate Boolean function f computable by some unknown small circuit from a known class of circuits, find in deterministic time poly(2n) a circuit C (no restriction on the type of C) computing f so that the size of C is less than the trivial circuit size 2n/n. We get nontrivial compression for functions computable by AC0circuits, (de Morgan) formulas, and (read-once) branching programs of the size for which the lower bounds for the corresponding circuit class are known. These compression algorithms rely on the structural characterizations of “easy” functions, which are useful both for proving circuit lower bounds and for designing “meta-algorithms” (such as Circuit-SAT). For (de Morgan) formulas, such structural characterization is provided by the “shrinkage under random restrictions” results [52], [21], strengthened to the “high-probability” version by [48], [26], [33]. We give a new, simple proof of the “high-probability” version of the shrinkage result for (de Morgan) formulas, with improved parameters. We use this shrinkage result to get both compression and #SAT algorithms for (de Morgan) formulas of size about n2. We also use this shrinkage result to get an alternative proof of the recent result by Komargodski and Raz [33] of the average-case lower bound against small (de Morgan) formulas. Finally, we show that the existence of any non-trivial compression algorithm for a circuit class C ⊆ P/poly would imply the circuit lower bound NEXP ⊈ C. This complements Williams's result [55] that any non-trivial Circuit-SAT algorithm for a circuit class C would imply a superpolynomial lower bound against C for a language in NEXP1.

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.

The Valiant-Vazirani Isolation Lemma provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: Given a Boolean circuit C on n input variables, the procedure outputs a new circuit C' on the same n input variables such that (i) every satisfying assignment of C' also satisfies C, and (ii) if C is satisfiable, then C' has exactly one satisfying assignment. In particular, if C is unsatisfiable, then (i) implies that C' is unsatisfiable. The Valiant-Vazirani procedure is randomized, and when C is satisfiable it produces a uniquely satisfiable circuit C' with probability Omega(1/n). Is it possible to have an efficient deterministic witness-isolating procedure? Or, at least, is it possible to improve the success probability of a randomized procedure to a large constant? We argue that the answer is likely `No'. More precisely, we prove that there exists a non-uniform randomized polynomial-time witness-isolating procedure with success probability bigger than 2/3 if and only if NP is in P/poly. Thus, an improved witness-isolating procedure would imply the collapse of the polynomial-time hierarchy. We establish similar results for other variants of witness isolation, such as reductions that remove all but an odd number of satisfying assignments of a satisfiable circuit. We also consider a black box setting of witness isolation that generalizes the setting of the Valiant-Vazirani Isolation Lemma, and give an upper bound of O(1/n) on the success probability for a natural class of randomized witness-isolating procedures.

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.

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 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

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 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.

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 propose a new approach towards derandomization in the uniform setting, where it is computationally hard to find possible mistakes in the simulation of a given probabilistic algorithm. The approach consists in combining both easiness and hardness complexity assumptions: if a derandomization method based on an easiness assumption fails, then we obtain a certain hardness test that can be used to remove error in BPP algorithms. As an application, we prove that every RP algorithm can be simulated by a zero-error probabilistic algorithm, running in expected subexponential time, that appears correct infinitely often (i.o.) to every efficient adversary. A similar result by Impagliazzo and Wigderson (1998) states that BPP allows deterministic subexponential-time simulations that appear correct with respect to any efficiently sampleable distribution i.o., under the assumption that EXP/spl ne/BPP; in contrast, our result does not rely on any unproven assumptions. As another application of our techniques, we get the following gap theorem for ZPP: either every RP algorithm can be simulated by a deterministic subexponential-time algorithm that appears correct i.o. to every efficient adversary, or EXP=ZPP. In particular this implies that if ZPP is somewhat easy, e.g., ZPP/spl sube/DTIME(2(n/sup c/)) for some fixed constant c, then RP is subexponentially easy in the uniform setting described above.

We study the complexity of the following circuit minimization problem: given the truth table of a Boolean function f and a parameter s, decide whether f can be realized by a Boolean circuit of size at most s.We argue why this problem is unlikely to be in P (or even in P/poly) by giving a number of surprising consequences of such an assumption.We also argue that proving this problem to be NP-complete (if it is indeed true) would imply proving strong circuit lower bounds for the class DTIME(2°('~)), which appears beyond the currently known techniques.Question: Is f,~ computable by a Boolean circuit of size at most sn?