Abstract A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the AM vs. NP problem). Both questions are intricately tied to lower bounds. Prominently, in both settings blackbox derandomization, i.e., derandomization through pseudorandom generators, has been shown equivalent to lower bounds for decision problems against circuits. Recently, Chen and Tell (FOCS'21) established nearequivalences in the BPP setting between whitebox derandomization and lower bounds for multi-bit functions against algorithms on almost-all inputs. The key ingredient is a technique to translate hardness into targeted hitting sets in an instance-wise fashion based on a layered arithmetization of the evaluation of a uniform circuit computing the hard function $$f$$ f on the given instance. Follow-up works managed to obtain full equivalences in the BPP setting by exploiting a compression property of classical pseudorandom generator constructions. In particular, Chen, Tell, and Williams (FOCS'23) showed that derandomization of BPP is equivalent to constructive lower bounds against algorithms that go through a compression phase. In this paper, we develop a corresponding technique for Arthur-Merlin protocols and establish similar near-equivalences in the AM setting. As an example of our results in the hardness-to-derandomization direction, consider a length-preserving function $$f$$ f computable by a nondeterministic algorithm that runs in time $$n^a$$ n a . We show that if every Arthur-Merlin protocol that runs in time $$n^c$$ n c for $$c=O(\log^2 a)$$ c = O ( log 2 a ) can only compute $$f$$ f correctly on finitely many inputs, then AM is in NP. We also obtain equivalences between constructive lower bounds against Arthur-Merlin protocols that go through a compression phase and derandomization of AM via targeted generators. Our main technical contribution is the construction of suitable targeted hitting-set generators based on probabilistically checkable proofs of proximity for nondeterministic computations. As a by-product of our constructions, we obtain the first result indicating that whitebox derandomization of AM may be equivalent to the existence of targeted hitting-set generators for AM, an issue raised by Goldreich (LNCS, 2011). By-products in the average-case setting include the first uniform hardness vs. randomness trade-offs for AM, as well as an unconditional mild derandomization result for AM.

We consider the following computational problem: Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the well-known problem of counting inversions in arrays originated in mathematical psychology. It has the evaluation of the Mann-Whitney statistic for detecting differences between distributions as a special case. We study the complexity of the problem in the comparison-query model, the standard model for problems like sorting, selection, and heap construction. The complexity depends heavily on the shape of the tree: for trees of unit depth, the problem is trivial; for many other shapes, we establish lower bounds close to the strongest known in the model, namely the lower bound of log2(n!) for sorting n items. For trees with n leaves we show, in increasing order of closeness to the sorting lower bound: (a) log2((α(1 — α)n)!) — O(log n) queries are needed whenever the tree has a subtree that contains a fraction α of the leaves. This implies a lower bound of for trees of degree k. (b) log2(n!) — O(log n) queries are needed in case the tree is binary. (c) log2(n!) — O(k log k) queries are needed for certain classes of trees of degree k, including perfect trees with even k. The lower bounds are obtained by developing two novel techniques for a generic problem Π in the comparison-query model and applying them to inversion minimization on trees. Both techniques can be described in terms of the Cayley graph of the symmetric group with adjacent-rank transpositions as the generating set, or equivalently, in terms of the edge graph of the permutahedron, the polytope spanned by all permutations of the vector (1, 2,…, n). Consider the subgraph consisting of the edges between vertices with the same value under Π. We show that the size of any decision tree for Π must be at least: (i) the number of connected components of this subgraph, and (ii) the factorial of the average degree of the complementary subgraph, divided by n. Lower bounds on query complexity then follow by taking the base-2 logarithm. Technique (i) represents a discrete analog of a classical technique in algebraic complexity and allows us to establish (c) and a tight lower bound for counting cross inversions, as well as unify several of the known lower bounds in the comparison-query model. Technique (ii) represents an analog of sensitivity arguments in Boolean complexity and allows us to establish (a) and (b). Along the way to proving (b), we derive a tight upper bound on the maximum probability of the distribution of cross inversions, which is the distribution of the Mann-Whitney statistic in the case of the null hypothesis. Up to normalization the probabilities alternately appear in the literature as the coefficients of polynomials formed by the Gaussian binomial coefficients, also known as Gaussian polynomials.

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance on shallow semi-unbounded circuits. A common approach employs small weight assignments that make the solution of minimum weight unique. The Isolation Lemma and other known procedures use $\Omega(n)$ random bits to generate weights of individual bitlength $O(\log n)$, where $n$ denotes the bitlength of solutions. We develop a derandomized version for both settings that uses $O((\log n)^{3/2})$ random bits and produces weights of bitlength $O((\log n)^{3/2})$ in logarithmic space. The construction allows us to show that every language in NL can be accepted by a nondeterministic machine that runs in polynomial time and $O((\log n)^{3/2})$ space,and has at most one accepting computation path on every input. Similarly, every language in LogCFL can be accepted by a nondeterministic machine equipped with a stack that does not count towards the space bound, that runs in polynomial time and $O((\log n)^{3/2})$ space, and that has at most one accepting computation path on every input. We also show that the existence of somewhat more restricted isolations for reachability on digraphs implies that NL can be decided in logspace with polynomial advice. A similar result holds for certifying acceptance on shallow semi-unbounded circuits and LogCFL.

We study the computational power of deciding whether a given truth table can be described by a circuit of a given size (the minimum circuit size problem, or MCSP for short) and of the variant denoted as MKTP, where circuit size is replaced by a polynomially related Kolmogorov measure. Prior to our work, all reductions from supposedly intractable problems to MCSP/MKTP hinged on the power of MCSP/MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of graph isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include linear code equivalence, permutation group conjugacy, and matrix subspace conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.

Björklund and Husfeldt developed a randomized polynomial time algorithm to solve the shortest two disjoint paths problem. Their algorithm is based on computation of permanents modulo 4 and the isolation lemma. In this paper, we consider the following generalization of the shortest two disjoint paths problem, and develop a similar algebraic algorithm. The shortest perfect $(A+B)$-path packing problem is: given an undirected graph $G$ and two disjoint node subsets $A,B$ with even cardinalities, find a shortest $|A|/2+|B|/2$ disjoint paths whose ends are both in $A$ or both in $B$. Besides its NP-hardness, we prove that this problem can be solved in randomized polynomial time if $|A|+|B|$ is fixed. Our algorithm basically follows the framework of Björklund and Husfeldt but uses a new technique: computation of hafnian modulo $2^k$ combined with Gallai's reduction from $T$-paths to matchings. We also generalize our technique for solving other path packing problems, and discuss its limitation.

Consider the following two-player communication process to decide a language L : The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x ; their goal is to decide cooperatively whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player. For any integer d ≥ 3 and positive real ε , we show that, if satisfiability for n -variable d -CNF formulas has a protocol of cost O ( nd − ε ), then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to its third level. The result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for ε = 0. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. By reduction, similar results hold for other NP-complete problems. For the vertex cover problem on n -vertex d -uniform hypergraphs, this statement holds for any integer d ≥ 2. The case d = 2 implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of O ( k 2 − ε ) edges unless coNP is in NP/poly, where k denotes the size of the deletion set. Kernels consisting of O ( k 2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.

Hardness against nondeterministic circuits is known to suffice for derandomizing Arthur-Merlin games. We show a result in the other direction - that hardness against nondeterministic circuits is *necessary* for derandomizing Arthur-Merlin games. In fact, we obtain an equivalence for a mild notion of derandomization: Arthur-Merlin games can be simulated in Sigma_2-SUBEXP (the sub exponential version of Sigma_2-P) with sub polynomial advice on infinitely many input lengths if and only if Sigma_2-E} (the linear-exponential version of Sigma_2-P) requires nondeterministic circuits of super polynomial size on infinitely many input lengths. Our equivalence result represents a full analogue of a similar result by Impagliazzo et al. in the deterministic setting: Randomized polynomial-time decision procedures can be simulated in NSUBEXP (the sub exponential version of NP) with sub polynomial advice on infinitely many input lengths if and only if NE (the linear-exponential version of NP) requires deterministic circuits of super polynomial size on infinitely many input lengths. A key ingredient in our proofs is improved Karp-Lipton style collapse results for nondeterministic circuits. The following are two instantiations that may be of independent interest: Assuming that Arthur-Merlin games can be derandomized in Sigma_2-P, we show that (i) PSPACE in NP/poly implies PSPACE in Sigma_2-P, and (ii) coNP in NP/poly implies PH in P^\Sigma_2-P.

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.

We study the locality of an extension of first-order logic that captures graph queries computable in ${AC}^0}$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the particular interpretation of the numerical predicates. We refer to such formulas as Arb-invariant first-order. We consider the two standard notions of locality, Gaifman and Hanf locality. Our main result gives a Gaifman locality theorem: An Arb-invariant first-order formula cannot distinguish between two tuples that have the same neighborhood up to distance $(\log n)^c$, where $n$ represents the number of elements in the structure and $c$ is a constant depending on the formula. When restricting attention to string structures, we achieve the same quantitative strength for Hanf locality. In both cases we show that our bounds are tight. We also present an application of our results to the study of regular languages. Our proof exploits the close connection between first-order formulas and the complexity class ${AC}^0}$ and hinges on the tight lower bounds for parity on constant-depth circuits.

This section of SIAM Journal on Computing contains extended versions of selected papers from the 43rd ACM Symposium on Theory of Computing (STOC), held June 6--8, 2011, in San Jose, California, as part of the fifth Federated Computing Research Conference (FCRC). The STOC proceedings contained 84 papers, which were selected from 304 submissions by the program committee, consisting of Ittai Abraham, Alexandr Andoni, Avrim Blum, Allan Borodin, Kousha Etessami, Lisa Fleischer, Venkatesan Guruswami, David Kempe, Frederic Magniez, Dieter van Melkebeek, Daniele Micciancio, Moni Naor, Kobbi Nissim, Seth Pettie, Ronitt Rubinfeld, Amir Shpilka, Ravi Sundaram, Eva Tardos, Prasad Tetali, Salil Vadhan (chair), Kasturi Varadarajan, Nisheeth Vishnoi, John Watrous, and Ryan Williams. Five of the STOC papers appear in this special section, each one expanded and fully refereed according to the high standards of the journal. They cover a diverse collection of topics: In “Distributed Verification and Hardness of Distributed Approximation,” Das Sarma, Holzer, Kor, Korman, Nanongkai, Pandurangan, Peleg, and Wattenhofer prove strong lower bounds on the power of distributed networks to verify their own properties (such as connectivity) and solve optimization problems such as computing approximate shortest paths or approximate min-cuts. They establish new connections between distributed computation and two-party communication complexity. The paper “Pareto Optimal Solutions for Smoothed Analysts” by Moitra and O'Donnell considers the smoothed complexity of discrete multi-objective optimization problems with $d+1$ linear objectives and with a solution space consisting of binary $n$-vectors. The authors show that, in a suitable smoothed analysis framework for such problems, the expected number of Pareto optimal solutions is at most $n^{2d}$. This improves greatly, as a function of the dimension d, an earlier upper bound established by Roeglin and Teng, which had roughly the form $n^{d^d}$. The paper “Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter” by Saxena and Seshadhri provides the first deterministic polynomial-time identity test for depth-3 arithmetic circuits with bounded top-fanin that only needs blackbox access to the circuit. Their construction has the feature that it works for arbitrary fields. In their paper “An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance,” Chakrabarti and Regev prove a lower bound establishing that the randomized communication complexity of the gap-Hamming-distance problem is linear. In obtaining this result, they have resolved an important and well-studied communication complexity problem having a fundamental connection to the data stream model of computation. Svensson's paper “Santa Claus Schedules Jobs on Unrelated Machines” breaks the barrier of 2 for efficiently approximating the minimum makespan for scheduling jobs on unrelated machines in the setting where all machines on which a given job can run take the same amount of time for that job. We thank the authors, the referees, and the full program committee for all their work, which made this special section possible.

We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula each variable occurs only a constant number of times and each subformula computes a multilinear polynomial. Before our work no subexponential-time deterministic algorithm was known for this class of formulae. We also present a deterministic algorithm that works in a blackbox fashion and runs in quasi-polynomial time in general, and polynomial time for constant depth. Finally, we extend our results and allow the inputs to be replaced with sparse polynomials. Our results encompass recent deterministic identity tests for sums of a constant number of read-once formulae, and for multilinear depth-four circuits.

Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player. For any integer d ≥ 3 and positive real ε we show that if satisfiability for n-variable d-CNF formulas has a protocol of cost O(nd-ε) then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to its third level. The result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for ε = 0. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. By reduction, similar results hold for other NP-complete problems. For the vertex cover problem on n-vertex d-uniform hypergraphs, the above statement holds for any integer d ≥ 2. The case d=2 implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of O(k2-ε) edges unless coNP is in NP/poly, where k denotes the size of the deletion set. Kernels consisting of O(k^2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.

In keeping with an annual tradition, this issue of the SIAM Journal on Computing contains extended versions of selected papers from the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2006), which was held May 21–23, 2006, in Seattle, Washington. The conference program included 78 papers selected by a program committee consisting of Scott Aaronson, Eli Ben-Sasson, Allan Borodin, David Eppstein, Sudipto Guha, Piotr Indyk, Jon Kleinberg, Tal Malkin, Frank McSherry, Dieter van Melkebeek, Michael Mitzenmacher, Assaf Naor, Rafail Ostrovsky, Toniann Pitassi, R. Ravi, Dana Ron, Amin Saberi, Amit Sahai, Rocco Servedio, and Madhu Sudan. Preliminary versions of these papers appeared in the conference proceedings published by ACM Press. This special issue contains 11 of these papers; the authors were invited by the program committee to prepare extended versions of their papers, which were then refereed according to the journal's high standards. In the process, these papers were considerably revised and expanded. Collectively, they represent some of the recent highlights from a broad cross-section of active areas within theoretical computer science, including randomness in computation, approximation algorithms and inapproximability, proof complexity, property testing, constraint satisfaction, quantum computing, algorithmic game theory, and high-dimensional geometric algorithms. In total, the six of us listed below handled the editing of these papers. We would like to thank all of the referees and the full program committee for their contributions to the preparation of this special issue.

We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following. Let $s(n)$ be any space-constructible function that is $Omega(log n)$ and such that $s(a n) = O(s(n))$ for all constants $a$, and let $s'(n)$ be any function that is $omega(s(n))$. - There exists a language computable by two-sided error randomized machines using $s'(n)$ space and one bit of advice that is not computable by two-sided error randomized machines using $s(n)$ space and $min(s(n),n)$ bits of advice. - There exists a language computable by zero-sided error randomized machines in space $s'(n)$ with one bit of advice that is not computable by one-sided error randomized machines using $s(n)$ space and $min(s(n),n)$ bits of advice. The condition that $s(a n)=O(s(n))$ is a technical condition satisfied by typical space bounds that are at most linear. We also obtain weaker results that apply to generic semantic models of computation.

We show that for any reasonable semantic model of computation and for any positive integer a and rationals 1 ≤ c < d, there exists a language computable in time n d with a bits of advice but not in time n c with a bits of advice. Our result implies the first such hierarchy theorem for randomized machines with zero-sided error, quantum machines with one- or zero-sided error, unambiguous machines, symmetric alternation, Arthur.Merlin games of any signature, etc. Our argument yields considerably simpler proofs of known hierarchy theorems with one bit of advice for randomized and quantum machines with two-sided error. Our paradigm also allows us to derive stronger separation results in which the machine with the smaller running time can receive more advice than the one with the larger running time. We present a unified way to derive such results for randomized and quantum machines with two-sided error and for randomized machines with one-sided error.

We show that for any reasonable semantic model of computation and for any positive integer a and rationals 1dwith a bits of advice but not in time ncwith a bits of advice. A semantic model is one for which there exists a computable enumeration that contains all machines in the model but may also contain others. We call such a model reasonable if it has an efficient universal machine that can be complemented within the model in exponential time and if it is efficiently closed under deterministic transducers. Our result implies the first such hierarchy theorem for randomized machines with zero-sided error, quantum machines with one- or zero-sided error, unambiguous machines, symmetric alternation, Arthur-Merlin games of any signature, etc. Our argument yields considerably simpler proofs of known hierarchy theorems with one bit of advice for randomized and quantum machines with two-sided error. Our paradigm also allows us to derive stronger separation results in a unified way. For models that have an efficient universal machine that can be simulated deterministically in exponential time and that are efficiently closed under randomized reductions with two-sided error, we establish the following: For any constants a and c, there exists a language computable in polynomial time with one bit of advice but not in time ncwith a log n bits of advice. The result applies to randomized and quantum machines with two-sided error. For randomized machines with one-sided error, our approach yields that for any constants a and c there exists a language computable in polynomial time with one bit of advice but not in time ncwith a (log n)1c/ bits of advice

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let ${{R_{\rm C}}}, {{R_{\rm Kt}}}, {{R_{\rm KS}}}, {{R_{\rm KT}}}$ be the sets of strings x having complexity at least $|x|/2$, according to the usual Kolmogorov complexity measure ${\mbox{\rm C}}$, Levin's time-bounded Kolmogorov complexity ${\mbox{\rm Kt}}$ [L. Levin, Inform. and Control, 61 (1984), pp. 15-37], a space-bounded Kolmogorov measure ${\mbox{\rm KS}}$, and a new time-bounded Kolmogorov complexity measure ${\mbox{\rm KT}}$, respectively. Our main results are as follows: \begin{remunerate} \item ${{R_{\rm KS}}}$ and ${{R_{\rm Kt}}}$ are complete for ${{\rm{PSPACE}}}$ and {\mbox{\rm EXP}}, respectively, under ${\mbox{\rm P/poly}}$-truth-table reductions. Similar results hold for other classes with ${{\rm{PSPACE}}}$-robust Turing complete sets. \item ${\mbox{\rm EXP}} = {\mbox{\rm NP}}^{{{R_{\rm Kt}}}}.$ \item ${{\rm{PSPACE}}} = {\mbox{\rm ZPP}}^{{{R_{\rm KS}}}} \subseteq {\mbox{\rm P}}^{{{R_{\rm C}}}}$. \item The Discrete Log, Factoring, and several lattice problems are solvable in ${\mbox{\rm BPP}}^{{{R_{\rm KT}}}}$. \end{remunerate} Our hardness result for ${{\rm{PSPACE}}}$ gives rise to fairly natural problems that are complete for ${{\rm{PSPACE}}}$ under ${\mbox{$\leq^{\rm p}_{\rm T}$}}$ reductions, but not under ${\mbox{$\leq^{\rm log}_{\rm m}$}}$ reductions. Our techniques also allow us to show that all computably enumerable sets are reducible to ${{R_{\rm C}}}$ via ${\mbox{\rm P/poly}}$-truth-table reductions. This provides the first "efficient" reduction of the halting problem to ${{R_{\rm C}}}$.

We establish the first polynomial‐strength time‐space lower bounds for problems in the linear‐time hierarchy on randomized machines with two‐sided error. We show that for any integer $\ell > 1$ and constant $c < \ell$, there exists a positive constant d such that QSAT$_{\ell}$ cannot be computed by such machines in time $n^c$ and space $n^d$, where QSAT$_{\ell}$ denotes the problem of deciding the validity of a quantified Boolean formula with at most $\ell - 1$ quantifier alternations. Moreover, d approaches 1/2 from below as c approaches 1 from above for $\ell = 2$, and d approaches 1 from below as c approaches 1 from above for $\ell \ge 3$. In fact, we establish the stronger result that for any constants $a \le 1$ and $c < 1 + (\ell - 1)a$, there exists a positive constant d such that linear‐time alternating machines using space $n^a$ and $\ell - 1$ alternations cannot be simulated by randomized machines with two‐sided error running in time $n^c$ and space $n^d$, where d approaches $a/2$ from below as c approaches 1 from above for $\ell = 2$, and d approaches a from below as c approaches 1 from above for $\ell \ge 3$. Corresponding to $\ell = 1$, we prove that there exists a positive constant d such that the set of Boolean tautologies cannot be decided by a randomized machine with one‐sided error in time $n^{1.759}$ and space $n^d$. As a corollary, this gives the same lower bound for satisfiability on deterministic machines, improving on the previously best known such result.

The language compression problem asks for succinct descriptions of the strings in a language A such that the strings can be efficiently recovered from their description when given a membership oracle for A. We study randomized and nondeterministic decompression schemes and investigate how close we can get to the information theoretic lower bound of $$\log {\left\| {A^{{ = n}} } \right\|}$$ for the description length of strings of length n. Using nondeterminism alone, we can achieve the information theoretic lower bound up to an additive term of $$O{\left( {{\left( {{\sqrt {\log {\left\| {A^{{ = n}} } \right\|}} } + \log n} \right)}\log n} \right)};$$ using both nondeterminism and randomness, we can make do with an excess term of $$O{\left( {\log ^{3} n} \right)}.$$ With randomness alone, we show a lower bound of $$n - \log {\left\| {A^{{ = n}} } \right\|} - O{\left( {\log n} \right)}$$ on the description length of strings in A of length n, and a lower bound of $$2 \cdot \log {\left\| {A^{{ = n}} } \right\|} - O(1)$$ on the length of any program that distinguishes a given string of length n in A from any other string. The latter lower bound is tight up to an additive term of $$O{\left( {\log n} \right)}.$$ The key ingredient for our upper bounds is the relativizable hardness versus randomness tradeoffs based on the Nisan–Wigderson pseudorandom generator construction.

We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive constant d such that no deterministic random-access Turing machine can solve satisfiability in time n c and space n d , where d approaches 1 when c does. On conondeterministic instead of deterministic machines, we prove the same for any constant c less than √2.Our lower bounds apply to nondeterministic linear time and almost all natural NP-complete problems known. In fact, they even apply to the class of languages that can be solved on a nondeterministic machine in linear time and space n 1/c .Our proofs follow the paradigm of indirect diagonalization. We also use that paradigm to prove time-space lower bounds for languages higher up in the polynomial-time hierarchy.

We derive a stronger consequence of $\mathsf{EXP}$ (deterministic exponential time) having polynomial-size circuits than was known previously, namely that for each language $L \in \mathsf{P}$ (polynomial time), and for each efficiently decidable error-correcting code E having nontrivial relative distance, there is a simulation of L in Merlin-Arthur polylogarithmic time that fools all deterministic polynomial-time adversaries for inputs that are codewords of E. Using the connection between circuit lower bounds and derandomization, we obtain uniform assumptions for derandomizing $\mathsf{BPP}$ (probabilistic polynomial time). Our results strengthen the space-randomness tradeoffs of Sipser [J. Comput. System Sci., 36 (1988), pp. 379--383], Nisan and Wigderson [J. Comput. System Sci.}, 49 (1994), pp. 149--167], and Lu [Comput. Complexity, 10 (2001), pp. 247--259]. We also consider a more quantitative notion of simulation, where the measure of success of the simulation is the fraction of inputs of a given length on which the simulation works. Among other results, we show that if there is no polynomial-time bound t such that $\mathsf{P}$ can be simulated well by Merlin-Arthur machines operating in time t, then for any $\epsilon > 0$ there is a simulation of $\mathsf{BPP}$ in $\mathsf{P}$ that works for all but $2^{n^{\epsilon}}$ inputs of length n. This is a uniform strengthening of a recent result of Goldreich and Wigderson [ Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science, 2002, pp. 209--223]. Finally, we give an unconditional simulation of multitape Turing machines operating in probabilistic time t by Turing machines operating in deterministic time o(2 t ). We show similar results for randomized $\mathsf{NC}^{1}$ circuits. Our proofs are based on a combination of techniques in the theory of derandomization with results on holographic proofs.

The language compression problem asks for succinct descriptions of the strings in a language A such that the strings can be efficiently recovered from their description when given a membership oracle for A. We study randomized and nondeterministic decompression schemes and investigate how close we can get to the information theoretic lower bound of log /spl par/A/sup = n//spl par/ for the description length of strings of length n. Using nondeterminism alone, we can achieve the information theoretic lower bound up to an additive term of 0((/spl radic/ /spl par/A/sup = n//spl par/ + log n)log n); using both nondeterminism and randomness, we can make do with an excess term of 0(log/sup 3/ n). With randomness alone, we show a lower bound of n - log /spl par/A/sup = n//spl par/ - 0(log n) on the description length of strings in A of length n, and a lower bound of 2/spl middot/log /spl par/A/sup = n//spl par/ - 0(1) on the length of any program that distinguishes a given string length n in A from any other string. The latter lower bound is tight up to an additive term of 0(log n). The key ingredient for our upper bounds is the relativizable hardness versus randomness trade offs based on the Nisan-Wigderson pseudorandom generator construction.

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.

Traditional hardness versus randomness results focus on time-efficient randomized decision procedures. We generalize these trade-offs to a much wider class of randomized processes. We work out various applications, most notably to derandomizing Arthur-Merlin games. We show that every language with a bounded round Arthur-Merlin game has subexponential size membership proofs for infinitely many input lengths unless exponential time coincides with the third level of the polynomial-time hierarchy (and hence the polynomial-time hierarchy collapses). Since the graph nonisomorphism problem has a bounded round Arthur-Merlin game, this provides the first strong evidence that graph nonisomorphism has subexponential size proofs. We also establish hardness versus randomness trade-offs for space bounded computation.

Introduces computational depth, a measure for the amount of "non-random" or "useful" information in a string, by considering the difference of various Kolmogorov complexity measures. We investigate three instantiations of computational depth: (1) basic computational depth, a clean notion capturing the spirit of C.H. Bennett's (1988) logical depth; (2) time-t computational depth and the resulting concept of shallow sets, a generalization of sparse and random sets based on low depth properties of their characteristic sequences (we show that every computable set that is reducible to a shallow set has polynomial-size circuits); and (3) distinguishing computational depth, measuring when strings are easier to recognize than to produce (we show that if a Boolean formula has a non-negligible fraction of its satisfying assignments with low depth, then we can find a satisfying assignment efficiently).

We show new tradeoffs for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time n/sup 1.618/ and space n/sup o(1)/. This improves recent results of Fortnow and of Lipton and Viglas. In general, for any constant a less than the golden ratio, we prove that satisfiability cannot be solved in time n/sup a/ and space n/sup /spl delta// for some positive constant b. Our techniques allow us to establish this result for b< 1/2 (/spl alpha/+2/a(2)-a). We can do better for a close to the golden ratio, for example, satisfiability cannot be solved by a random-access Turing machine using n/sup 1.46/ time and n/sup .11/ space. We also show tradeoffs for nondeterministic linear time computations using sublinear space. For example, there exists a language computable in nondeterministic linear time and n/sup 619/ space that cannot be computed in deterministic n/sup 1.618/ time and n/sup o(1)/ space. Higher up the polynomial-time hierarchy we can get better bounds. We show that linear-time /spl Sigma//sub l/-computations require essentially n/sup l/ time on deterministic machines that use only n/sup o(1)/ space. We also show new lower bounds on conondeterministic versus nondeterministic computation.

A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from exponential space by showing that all Turing complete sets for certain levels of the exponential-time hierarchy are autoreducible but there exists some Turing complete set for doubly exponential space that is not. Although we already knew how to separate these classes using diagonalization, our proofs separate classes solely by showing they have different structural properties, thus applying Post's program to complexity theory. We feel such techniques may prove unknown separations in the future. In particular, if we could settle the question as to whether all Turing complete sets for doubly exponential time are autoreducible, we would separate either polynomial time from polynomial space, and nondeterministic logarithmic space from nondeterministic polynomial time, or else the polynomial-time hierarchy from exponential time. We also look at the autoreducibility of complete sets under nonadaptive, bounded query, probabilistic, and nonuniform reductions. We show how settling some of these autoreducibility questions will also lead to new complexity class separations.

We introduce resource-bounded betting games and propose a generalization of Lutz's resource-bounded measure in which the choice of the next string to bet on is fully adaptive. Lutz's martingales are equivalent to betting games constrained to bet on strings in lexicographic order. We show that if strong pseudorandom number generators exist, then betting games are equivalent to martingales for measure on E and EXP. However, we construct betting games that succeed on certain classes whose Lutz measures are important open problems: the class of polynomial-time Turing-complete languages in EXP and its superclass of polynomial-time Turing-autoreducible languages. If an EXP-martingale succeeds on either of these classes, or if betting games have the "finite union property" possessed by Lutz's measure, one obtains the nonrelativizable consequence $\mbox{BPP} \neq \mbox{EXP}$. We also show that if $\mbox{EXP} \neq \mbox{MA}$, then the polynomial-time truth-table-autoreducible languages have Lutz measure zero, whereas if $\mbox{EXP} = \mbox{BPP}$, they have measure one.

We investigate the frequency of complete sets for various complexity classes within EXP under several polynomial-time reductions in the sense of resource bounded measure. We show that these sets are scarce: The sets that are complete under /spl les/(n/sup /spl alpha//-tt/sup -/)/sup P/ reductions for NP, the levels of the polynomial-time hierarchy, and PSPACE have p/sub 2/-measure zero for any constant /spl alpha/<1. The /spl les/(n/sup c/-T)/sup P/-complete sets for EXP have p/sub 2/-measure zero for any constant c. Assuming MA/spl ne/EXP, the /spl les//sub tt//sup P/-complete sets for EXP have p-measure zero. A key ingredient is the Small Span Theorem, which states that for any set A in EXP at least one of its lower span (i.e., the sets that reduce to A) or its upper span (i.e., the sets that A reduces to) has p/sub 2/-measure zero. Previous to our work, the theorem was only known to hold for /spl les//sub btt//sup p/-reductions. We establish it for /spl les/(n/sup 0/(1)-tt)/sup p/-reductions.

We prove that there is no sparse hard set for P under logspace computable bounded truth-table reductions unless P=L. In case of reductions computable in NC/sup 1/, the collapse goes down to P=NC/sup 1/. We generalize this result by parameterizing the sparseness condition, the space bound and the number of queries of the reduction, apply the proof technique to NL and L, and extend all these theorems to two-sided error randomized reductions in the multiple access model, for which we also obtain new results for NP.