The algebrization barrier, proposed by Aaronson and Wigderson (STOC '08, ToCT '09), captures the limitations of many complexity-theoretic techniques based on arithmetization. Notably, several circuit lower bounds that overcome the relativization barrier (Buhrman-Fortnow-Thierauf, CCC '98; Vinodchandran, TCS '05; Santhanam, STOC '07, SICOMP '09) remain subject to the algebrization barrier. In this work, we establish several new algebrization barriers to circuit lower bounds by studying the communication complexity of the following problem, called XOR-Missing-String: For m < 2^{n/2}, Alice gets a list of m strings x₁, … , x_m ∈ {0, 1}ⁿ, Bob gets a list of m strings y₁, … , y_m ∈ {0, 1}ⁿ, and the goal is to output a string s ∈ {0, 1}ⁿ that is not equal to x_i⊕ y_j for any i, j ∈ [m]. 1) We construct an oracle A₁ and its multilinear extension A₁̃ such that PostBPE^{A₁̃} has linear-size A₁-oracle circuits on infinitely many input lengths. That is, proving PostBPE ̸ ⊆ i.o.- SIZE[O(n)] requires non-algebrizing techniques. This barrier follows from a PostBPP communication lower bound for XOR-Missing-String. This is in contrast to the well-known algebrizing lower bound MA_E (⊆ PostBPE) ̸ ⊆ P/_poly. 2) We construct an oracle A₂ and its multilinear extension A₂̃ such that BPE^{A₂̃} has linear-size A₂-oracle circuits on all input lengths. Previously, a similar barrier was demonstrated by Aaronson and Wigderson, but in their result, A₂̃ is only a multiquadratic extension of A₂. Our results show that communication complexity is more useful than previously thought for proving algebrization barriers, as Aaronson and Wigderson wrote that communication-based barriers were "more contrived". This serves as an example of how XOR-Missing-String forms new connections between communication lower bounds and algebrization barriers. 3) Finally, we study algebrization barriers to circuit lower bounds for MA_E. Buhrman, Fortnow, and Thierauf proved a sub-half-exponential circuit lower bound for MA_E via algebrizing techniques. Toward understanding whether the half-exponential bound can be improved, we define a natural subclass of MA_E that includes their hard MA_E language, and prove the following result: For every super-half-exponential function h(n), we construct an oracle A₃ and its multilinear extension A₃̃ such that this natural subclass of MA_E^{A₃̃} has h(n)-size A₃-oracle circuits on all input lengths. This suggests that half-exponential might be the correct barrier for MA_E circuit lower bounds w.r.t. algebrizing techniques.

In this work, we propose a new bounded arithmetic theory, denoted APX1, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer science. Under plausible assumptions, APX1 is strictly weaker than previously proposed frameworks, such as the theory APC1 introduced in the seminal work of Jeřábek (2007). From a computational standpoint, APX1 is closely tied to approximate counting and to the central question in derandomization, the prBPP versus prP problem, whereas APC1 is linked to the dual weak pigeonhole principle and to the existence of Boolean functions with exponential circuit complexity.

We show that there is a language in \(\textsf{S}_2\textsf {E}\) (symmetric exponential time) that requires circuit complexity at least \(2^n/n\) on every input length. In particular, the above also implies the same near-maximum circuit lower bounds for \(\Sigma _2\textsf {E}\cap \Pi _2\textsf {E}\) and \(\mathsf {ZPE}^{\textsf {NP}}\) . Our proofs relativise. Previously, only “half-exponential” circuit lower bounds for the aforementioned complexity classes were known, and the smallest complexity class known to require exponential circuit complexity was \(\Delta _3\textsf {E}= \textsf {E}^{\Sigma _2\textsf{P}}\) (Miltersen, Vinodchandran, and Watanabe COCOON’99). Our circuit lower bounds are corollaries of an unconditional zero-error pseudodeterministic algorithm with an \(\textsf {NP}\) oracle that solves the Range Avoidance problem. This algorithm also implies unconditional pseudodeterministic \(\textsf {FZPP}^{\textsf {NP}}\) constructions for Ramsey graphs, rigid matrices, two-source extractors, linear codes, and \(\mathrm{K}^{\mathrm{poly}}\) -random strings with nearly optimal parameters.

A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser [ 16 ] posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time. We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an unconditional polynomial-time randomized algorithm B such that, for infinitely many values of n , \(B(1^n)\) outputs a canonical n -bit prime \(p_n\) with high probability. More generally, we prove that for every dense property Q of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying Q . This improves upon a subexponential-time construction of Oliveira and Santhanam [ 49 ]. Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell [ 11 ], using a variant of the Shaltiel–Umans generator [ 51 ].

Transformers, especially the decoder-only variants, are the backbone of most modern large language models. Yet, we have a very limited understanding of their limitations (i.e., what tasks they cannot solve) besides the simplest 1-layer case. Due to the difficulty of analyzing multi-layer models, all previous work relies on unproven complexity conjectures to show limitations for multi-layer Transformers. In this work, we prove the first unconditional lower bound against multilayer decoder-only transformers. For any constant L, we prove that any L-layer decoder-only transformer needs a polynomial model dimension $\left(n^{\Omega(1)}\right)$ to perform sequential composition of L functions over an input of n tokens. As a consequence, our results give: (1) the first depthwidth trade-off for multi-layer transformers, exhibiting that the L-step composition task is exponentially harder for L-layer models compared to $(L+1)$-layer ones; (2) an unconditional separation between encoder and decoder, exhibiting a hard task for decoders that can be solved by an exponentially shallower and smaller encoder; (3) a provable advantage of chain-of-thought, exhibiting a task that becomes exponentially easier when the model is allowed to produce an intermediate sequence of tokens before outputting the final answer. On the technical side, we propose the multi-party autoregressive communication model that abstracts the key aspects of a decoder-only Transformer. In particular, lower bounds within this communication model imply lower bounds against decoder-only transformers, independent of their implementation details. To prove lower bounds in this communication model, we also introduce a new proof technique that finds a certain indistinguishable decomposition of all possible inputs iteratively. We believe our new communication model and proof techniques will be helpful to understand the computational power of transformers further.

Large language models (LLMs) frequently generate hallucinations—content that deviates from factually inaccurate or deviates from provided context—posing challenges for diagnosis. However, diagnosing the causes of hallucination is challenging due to the complex interplay of underlying causes. This paper introduces a framework to systematically understand the sources of hallucination behavior in large language models. Our key insight is that hallucinations arise when more frequent but non-factual associations outweigh faithful ones. Through theoretical and empirical analyses, we demonstrate that decoder-only transformers effectively function as subsequence embedding models, with the fully-connected layers encoding input-output associations. We propose a tracing algorithm that identifies causal subsequences by analyzing hallucination probabilities across randomized input contexts. Experiments show our method outperforms standard attribution techniques in identifying hallucination causes and is supported by evidence from the model’s training corpus. This work provides a unified perspective on hallucinations and a robust framework for their cause and analysis.

STOC ’25, Prague, Czechia

We show that there is a constant $k$ such that Buss's intuitionistic theory $\mathsf{IS}^1_2$ does not prove that SAT requires co-nondeterministic circuits of size at least $n^k$. To our knowledge, this is the first unconditional unprovability result in bounded arithmetic in the context of worst-case fixed-polynomial size circuit lower bounds. We complement this result by showing that the upper bound $\mathsf{NP} \subseteq \mathsf{coNSIZE}[n^k]$ is unprovable in $\mathsf{IS}^1_2$. In order to establish our main result, we obtain new unconditional lower bounds against refuters that might be of independent interest. In particular, we show that there is no efficient refuter for the lower bound $\mathsf{NP} \nsubseteq \mathsf{i.o.}\text{-}\mathsf{coNP}/\mathsf{poly}$, addressing in part a question raised by Atserias (2006).

Abstract. For a matrix [Formula: see text] over a field [Formula: see text], its rank-[Formula: see text] rigidity, denoted by [Formula: see text], is the minimum Hamming distance from [Formula: see text] to a matrix of rank at most [Formula: see text] over [Formula: see text]. A central open challenge in complexity theory is to give explicit constructions of rigid matrices for a variety of parameter settings. In this work, building on Williams’ seminal connection between circuit-analysis algorithms and lower bounds [ J. ACM, 61 (2014), 2], we give a construction of rigid matrices in [Formula: see text]. Letting [Formula: see text] be a prime power, we show that there is an absolute constant [Formula: see text] such that, for all constants [Formula: see text], there is a [Formula: see text] machine [Formula: see text] such that, for infinitely many [Formula: see text]’s, [Formula: see text] outputs a matrix [Formula: see text] with [Formula: see text] over [Formula: see text]. Using known connections between matrix rigidity and other topics in complexity theory, we derive several consequences of our constructions, including that there is a function [Formula: see text] such that [Formula: see text]. Previously, it was open whether [Formula: see text]. For all [Formula: see text], there is a [Formula: see text] machine [Formula: see text] such that, for infinitely many [Formula: see text]’s, [Formula: see text] outputs an [Formula: see text] matrix [Formula: see text] whose linear transformation requires depth-2 [Formula: see text]-linear circuits of size [Formula: see text]. The previous best lower bound for an explicit family of [Formula: see text] matrices over [Formula: see text] was only [Formula: see text], for asymptotically good error correcting codes.

Abstract. Following the seminal work of [R. R. Williams, J. ACM, 61 (2014)], in a recent breakthrough, [C. D. Murray and R. R. Williams, STOC 2018] proved that [Formula: see text] (nondeterministic quasi-polynomial time) does not have polynomial-size [Formula: see text] circuits (constant depth circuits consisting of [Formula: see text]/[Formula: see text]/[Formula: see text] gates for a fixed constant [Formula: see text], a frontier class in circuit complexity). We strengthen the above lower bound to an average-case one, by proving that for all constants [Formula: see text], there is a language in [Formula: see text] that cannot be [Formula: see text]-approximated by polynomial-size [Formula: see text] circuits. Our work also improves the average-case lower bound for [Formula: see text] against polynomial-size [Formula: see text] circuits by [R. Chen, I. C. Oliveira, and R. Santhanam, LATIN 2018, pp. 317–330]. Our new lower bound builds on several interesting components, including the following: 1. Barrington’s theorem and the existence of an [Formula: see text]-complete language that is random self-reducible. 2. The subexponential witness-size lower bound for [Formula: see text] against [Formula: see text] and the conditional nondeterministic pseudorandom generator (PRG) construction in [R. R. Williams, SIAM J. Comput., 45 (2016), pp. 497–529]. 3. An “almost” almost-everywhere [Formula: see text] average-case lower bound (which strengthens the corresponding worst-case lower bound in [C. D. Murray and R. R. Williams, STOC 2018]). 4. A [Formula: see text]-complete language that is downward self-reducible, same-length checkable, error-correctable, and paddable. Moreover, all its reducibility properties have corresponding low-depth nonadaptive oracle circuits. Our construction builds on [L. Trevisan and S. P. Vadhan, Comput. Complexity, 16 (2007), pp. 331–364]. Like other lower bounds proved via the “algorithmic approach,” the only property of [Formula: see text] exploited by us is the existence of a nontrivial [Formula: see text] algorithm for [Formula: see text] [R. R. Williams, J. ACM, 61 (2014)]. Therefore, for any typical circuit class [Formula: see text], our results apply to [Formula: see text] as well if a nontrivial [Formula: see text] (in fact, [Formula: see text]) algorithm for [Formula: see text] is discovered.

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are necessary to prove a given theorem. In this work, we systematically explore the reverse mathematics of complexity lower bounds. We explore reversals in the setting of bounded arithmetic, with Cook's theory PV1 as the base theory, and show that several natural lower bound statements about communication complexity, error correcting codes, and Turing machines are equivalent to widely investigated combinatorial principles such as the weak pigeonhole principle for polynomial-time functions and its variants. As a consequence, complexity lower bounds can be formally seen as fundamental mathematical axioms with far-reaching implications. The proof-theoretic equivalence between complexity lower bound statements and combinatorial principles yields several new implications for the (un)provability of lower bounds. Among other results, we derive the following consequences: • Under a plausible cryptographic assumption, the classical single-tape Turing machine (n2)-time lower bound for Palindrome is unprovable in Jerabek's theory APC1. The conditional unprovability of this simple lower bound goes against the intuition shared by some researchers that most complexity lower bounds could be established in APC1. • While APC1 proves one-way communication lower bounds for Set Disjointness, it does not prove one-way communication lower bounds for Equality, under a plausible cryptographic assumption. • An amplification phenomenon connected to the (un)provability of some lower bounds, under which a quantitatively weak lower bound is provable if and only if a stronger (and often tight) nclower bound is provable. • Feasibly definable randomized algorithms can be feasibly defined deterministically (APC1 is over PV1) if and only if one-way communication complexity lower bound for Set Disjointness are provable in PV1.

We show that there is a language in S2E/1 (symmetric exponential time with one bit of advice) with circuit complexity at least 2n/n. In particular, the above also implies the same near-maximum circuit lower bounds for the classes Σ2E, (Σ2E∩Π2E)/1, and ZPENP/1. Previously, only ”half-exponential” circuit lower bounds for these complexity classes were known, and the smallest complexity class known to require exponential circuit complexity was Δ3E = EΣ2P (Miltersen, Vinodchandran, and Watanabe COCOON’99).

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs fool width-3 programs, constant-width regular programs, and unbounded-width permutation programs with a single accepting vertex. In all three cases, the seed length is $\widetilde{O}(\log n \cdot \sqrt{\log (1 / \varepsilon)}+\log (1 / \varepsilon))$, where n is the length of the program and $\varepsilon$ is the error of the WPRG. For comparison, for all three of these models, the best explicit unweighted PRGs known have seed length $\widetilde{O}(\log n$. $\log (1 / \varepsilon)$) (Meka, Reingold, and Tal STOC 2019; Braverman, Rao, Raz, and Yehudayoff SICOMP 2014; Hoza, Pyne, and Vadhan ITCS 2021). Our WPRG seed length is superior when $\varepsilon$ is small. For the case of unbounded-width permutation programs, Pyne and Vadhan previously constructed a WPRG with a seed length that is similar to ours (CCC 2021), but their seed length has an extra additive $\log ^{3 / 2} n$ term, so our WPRG is superior when $\varepsilon \gg 1 / n$. Our results are based on a new, general framework for error reduction. Our framework builds on the remarkable recent work by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020) that gave a near-logarithmic space algorithm for estimating random walk probabilities in Eulerian digraphs with high precision. Our framework centers around the “inverse analysis” of random walks and a key combinatorial structure termed “shortcut graphs.” Using our new framework and the recent notion of singular value approximation (Ahmadinejad, Peebles, Pyne, Sidford, and Vadhan arXiv 2023), we also present an alternative, simpler proof of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan’s main theorem. Compared to the original proof, our new proof avoids much of the sophisticated machinery that was imported from recent work on fast Laplacian solvers.

A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser [1] posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time. We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an unconditional polynomial-time randomized algorithm B such that, for infinitely many values of $n, B\left(1^{n}\right)$ outputs a canonical n-bit prime $p_{n}$ with high probability. More generally, we prove that for every dense property Q of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying Q. This improves upon a subexponential-time construction of Oliveira and Santhanam [2]. Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell [3], using a variant of the Shaltiel-Umans generator [4].

We establish an equivalence between two algorithmic tasks: derandomization, the deterministic simulation of probabilistic algorithms; and refutation, the deterministic construction of inputs on which a given probabilistic algorithm fails to compute a certain hard function. We prove that refuting low-space probabilistic streaming algorithms which attempt to compute functions $f \in \mathcal{F P}$ is equivalent to proving that $\operatorname{pr} \mathcal{B P} \mathcal{P}=\operatorname{pr} \mathcal{P}$, even in cases where a lower bound for f against such streaming algorithms (without a refuter) is already unconditionally known. We also demonstrate the generality of our connection between refutation and derandomization, by establishing connections between refuting classes of constant-depth circuits of sublinear size and derandomizing constant-depth circuits of polynomial size with threshold gates (i.e., $\mathcal{T C}^{0}$). Our connection generalizes and strengthens recent work on the characterization of derandomization. In particular, the refuter framework allows to directly compare several recent works to each other and to our work, as well as to chart a path for further progress. Along the way, we also improve the targeted hitting-set generator of Chen and Tell (FOCS 2021), showing that its translation of hardness to pseudorandomness scales down to $\mathcal{T C}^{0}$.

We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, showing that they require linear space to guarantee a better-than-2 approximation [50, 52]. This result relies on a lower bound for the cycle-finding problem, showing that it is hard for a one-pass streaming algorithm to find a cycle in a union of matchings. The end-goal of our research is to prove a similar lower bound for multi-pass streaming algorithms that guarantee a better-than-2 approximation for Max-Cut, a highly challenging open problem. In this paper, we take a significant step in this direction, showing that even o(log n)-pass streaming algorithms need nΩ(1) space to solve the cycle-finding problem. Our proof is quite involved, dividing the cycles in the graph into “short” and “long” cycles, and using tailor-made lower bound techniques to handle each case.

What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of derandomizing interactive proofs systems.

Abstract In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include: Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time $$\tilde{O}(n)$$ O~(n) . Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in $$\tilde{O}(n^{1.5})$$ O~(n1.5) time (that is, there is a proof system with proofs of length $$\tilde{O}(n^{1.5})$$ O~(n1.5) and a deterministic verifier running in $$\tilde{O}(n^{1.5})$$ O~(n1.5) time). Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time $${\tilde{O}}(n^{\lceil k/2\rceil })$$ O~(n⌈k/2⌉) (where $$k\ge 3$$ k≥3 ). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time $${\tilde{O}}(m)$$ O~(m) . Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk. Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time $$\tilde{O}(n^2)$$ O~(n2) . Note this is optimal, as the matrix can have $$\Omega (n^2)$$ Ω(n2) nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an $$\tilde{O}(n^{2.94})$$ O~(n2.94) nondeterministic time algorithm. Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time $$2^{n/2 - n/O(k)}$$ 2n/2-n/O(k) . We also observe an algebrization barrier for the previous $$2^{n/2}\cdot \textrm{poly}(n)$$ 2n/2·poly(n) -time Merlin–Arthur protocol of R. Williams [CCC’16] for $$\#$$ # SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running in $$2^{n/2}/n^{\omega (1)}$$ 2n/2/nω(1) time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol. Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time $$2^{4n/5}\cdot \textrm{poly}(n)$$ 24n/5·poly(n) . Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in $$2^{2n/3}\cdot \textrm{poly}(n)$$ 22n/3·poly(n) time. Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time $$2^{n/3}\cdot \textrm{poly}(n)$$ 2n/3·poly(n)

The Exponential-Time Hypothesis (ETH) is a strengthening of the 𝒫 ≠ 𝒩𝒫 conjecture, stating that 3- SAT on n variables cannot be solved in (uniform) time 2 εċ n , for some ε > 0. In recent years, analogous hypotheses that are “exponentially strong” forms of other classical complexity conjectures (such as 𝒩𝒫⊈ ℬ𝒫𝒫 or co 𝒩𝒫⊈𝒩𝒫) have also been introduced and have become widely influential. In this work, we focus on the interaction of exponential-time hypotheses with the fundamental and closely related questions of derandomization and circuit lower bounds . We show that even relatively mild variants of exponential-time hypotheses have far-reaching implications to derandomization, circuit lower bounds, and the connections between the two. Specifically, we prove that: (1) The Randomized Exponential-Time Hypothesis (rETH) implies that ℬ𝒫𝒫 can be simulated on “average-case” in deterministic (nearly-)polynomial-time (i.e., in time 2 Õ(log( n )) = n loglog( n ) O(1) ). The derandomization relies on a conditional construction of a pseudorandom generator with near-exponential stretch (i.e., with seed length Õ(log ( n ))); this significantly improves the state-of-the-art in uniform “hardness-to-randomness” results, which previously only yielded pseudorandom generators with sub-exponential stretch from such hypotheses. (2) The Non-Deterministic Exponential-Time Hypothesis (NETH) implies that derandomization of ℬ𝒫𝒫 is completely equivalent to circuit lower bounds against ℰ, and in particular that pseudorandom generators are necessary for derandomization. In fact, we show that the foregoing equivalence follows from a very weak version of NETH, and we also show that this very weak version is necessary to prove a slightly stronger conclusion that we deduce from it. Last, we show that disproving certain exponential-time hypotheses requires proving breakthrough circuit lower bounds. In particular, if CircuitSAT for circuits over n bits of size poly(n) can be solved by probabilistic algorithms in time 2 n /polylog(n) , then ℬ𝒫ℰ does not have circuits of quasilinear size.

The leading technical approach in uniform hardness-to-randomness in the last two decades faced several well-known barriers that caused results to rely on overly strong hardness assumptions, and yet still yield suboptimal conclusions. In this work we show uniform hardness-to-randomness results that simultaneously break through all of the known barriers. Specifically, consider any one of the following three assumptions:1)For some $\epsilon>0$ there exists a function f computable by uniform circuits of size $2^{O(n)}$ and depth $2^{o(n)}$ such that f is hard for probabilistic time $2^{\epsilon n}$.2)For every $c\in \mathbb{N}$ there exists a function f computable by logspace-uniform circuits of polynomial size and depth n2such that every probabilistic algorithm running in time ncfails to compute f on $\mathrm{a}(1/n)$-fraction of the inputs.3)For every $c\in \mathbb{N}$ there exists a logspace-uniform family of arithmetic formulas of degree n2over a field of size poly $(n)$ such that no algorithm running in probabilistic time nccan evaluate the family on a worst-case input. Assuming any of these hypotheses, where the hardness is for every sufficiently large input length $n\in \mathbb{N}$, we deduce that $\mathcal{R}\mathcal{P}$ can be derandomized in polynomial time and on all input lengths, on average. Furthermore, under the first assumption we also show that $\mathcal{B}\mathcal{P}\mathcal{P}$ can be derandomized in polynomial time, on average and on all input lengths, with logarithmically many advice bits. On the way to these results we also resolve two related open problems. First, we obtain an optimal worst-case to average-case reduction for computing problems in linear space by uniform probabilistic algorithms; this result builds on a new instance checker based on the doubly efficient proof system of Goldwasser, Kalai, and Rothblum (J. ACM, 2015). Secondly, we resolve the main open problem in the work of Carmosino, Impagliazzo and Sabin (ICALP 2018), by deducing derandomization from weak and general fine-grained hardness hypotheses. The full version of this paper is available online [5].

We consider low-space algorithms for the classic Element Distinctness problem: given an array of n input integers with O(log n) bit-length, decide whether or not all elements are pairwise distinct. Beame, Clifford, and Machmouchi [FOCS 2013] gave an Õ(n1.5)-time randomized algorithm for Element Distinctness using only O(log n) bits of working space. However, their algorithm assumes a random oracle (in particular, read-only random access to polynomially many random bits), and it was asked as an open question whether this assumption can be removed. In this paper, we positively answer this question by giving an Õ(n1.5)-time randomized algorithm using O(log3 n log log n) bits of space, with one-way access to random bits. As a corollary, we also obtain a poly(n)-space O∗(20.86n)-time randomized algorithm for the Subset Sum problem, removing the random oracles required in the algorithm of Bansal, Garg, Nederlof, and Vyas [STOC 2017]. The main technique underlying our results is a pseudorandom hash family based on iterative restrictions, which can fool the cycle-finding procedure in the algorithms of Beame et al. and Bansal et al.

Hardness magnification reduces major complexity separations (such as EXP ⊈ NC 1 ) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [ 11 , 13 , 14 , 40 , 42 , 43 , 46 ] have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier than Q , while Q itself is susceptible to lower bounds, but these are not yet sufficient for magnification. In this work, we provide more examples of this phenomenon and investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program: – Does hardness magnification avoid the natural proofs barrier of Razborov and Rudich [ 51 ] ? – Can we adapt known lower-bound techniques to establish the desired lower bound for Q ? We establish that some instantiations of hardness magnification overcome the natural proofs barrier in the following sense: slightly superlinear-size circuit lower bounds for certain versions of the minimum circuit-size problem imply the non-existence of natural proofs. As the non-existence of natural proofs implies the non-existence of efficient learning algorithms, we show that certain magnification theorems not only imply strong worst-case circuit lower bounds but also rule out the existence of efficient learning algorithms. Hardness magnification might sidestep natural proofs, but we identify a source of difficulty when trying to adapt existing lower-bound techniques to prove strong lower bounds via magnification. This is captured by a locality barrier : existing magnification theorems unconditionally show that the problems Q considered above admit highly efficient circuits extended with small fan-in oracle gates, while lower-bound techniques against weak circuit models quite often easily extend to circuits containing such oracles. This explains why direct adaptations of certain lower bounds are unlikely to yield strong complexity separations via hardness magnification.

In a recent breakthrough, [C. Murray and R. R. Williams, STOC 2018, ACM, New York, 2018, pp. 890--901] proved that ${NQP} = {NTIME}[n^{{polylog}(n)}]$ cannot be computed by polynomial-size ${ACC}^0$ circuits (constant-depth circuits consisting of ${AND}$/${OR}$/${MOD}_m$ gates for a fixed constant $m$, a frontier class in circuit complexity). This was recently strengthened by [L. Chen, FOCS 2019, IEEE, Piscataway, NJ, 2019, pp. 1281--1304] to that ${NQP}$ cannot be $(1/2+1/{polylog}(n))$-approximated by polynomial-size ${ACC}^0$ circuits. In this work we will prove that ${NQP}$ cannot be $(1/2+1/n^{\omega(1)})$-approximated by polynomial-size ${ACC}^0$ circuits. As a straightforward application, we obtain an infinitely often nondeterministic pseudorandom generator for polysize ${ACC}^0$ circuits with sub-polynomial seed length. More generally, we establish a connection showing that, for a typical circuit class $\mathscr{C}$, nontrivial deterministic algorithms estimating the acceptance probability of $\mathscr{C}$ circuits imply strong ($1/2 + 1/n^{\omega(1)}$) average-case lower bounds against $\mathscr{C}$ circuits. We also apply this connection to prove new lower bounds against several subclasses of ${\sf TC}^0$ circuits (constant-depth circuits consisting entirely of majority gates), and show that nontrivial derandomization of ${MAJ} \circ {MAJ}$ would imply worst-case lower bounds for ${TC}^0_3$ (${MAJ} \circ{MAJ} \circ {MAJ}$), suggesting that ${TC}^0_3$ lower bounds are probably within reach. Our two new important technical ingredients are (1) techniques from cryptography in ${NC}^0$ [B. Applebaum, Y. Ishai, and E. Kushilevitz, SIAM J. Comput., 36 (2006), pp. 845--888], and (2) probabilistic checkable proofs of proximity with ${NC}^1$-computable proofs.

For a complexity class C and language L, a constructive separation of “L is not in C” gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every C-algorithm attempting to decide L. We study the questions: Which lower bounds can be made constructive? What are the consequences of constructive separations? We build a case that “constructiveness” serves as a dividing line between many weak lower bounds we know how to prove, and strong lower bounds against P, ZPP, and BPP. Put another way, constructiveness is the opposite of a complexity barrier: it is a property we want lower bounds to have. Our results fall into three broad categories. 1. For many separations, making them constructive would imply breakthrough lower bounds. Our first set of results shows that, for many well-known lower bounds against streaming algorithms, one-tape Turing machines, and query complexity, as well as lower bounds for the Minimum Circuit Size Problem, making these lower bounds constructive would imply break-through separations ranging from “EXP not equal to BPP” to even “P not equal to NP”. 2. Most conjectured uniform separations can be made constructive. Our second set of results shows that for most major open problems in lower bounds against P, ZPP, and BPP, including “P not equal to NP”, “P not equal to PSPACE”, “P not equal to PP”, “ZPP not equal to EXP”, and “BPP not equal to NEXP”, any proof of the separation would further imply a constructive separation. Our results generalize earlier results for “P not equal to NP” [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and “BPP not equal to NEXP” [Dolev, Fandina and Gutfreund, CIAC 2013]. Thus any proof of these strong lower bounds must also yield a constructive version, compared to many weak lower bounds we currently know. 3. Some separations cannot be made constructive. Our third set of results shows that certain complexity separations cannot be made constructive. We observe that for all super-polynomially growing functions$\mathbf{t}$, there are no constructive separations for detecting high t-time Kolmogorov complexity (a task which is known to be not in P) from any complexity class, unconditionally. We also show that under plausible conjectures, there are languages in NP -$\mathbf{P}$for which there are no constructive separations from any complexity class.

We propose a new approach to the hardness-to-randomness framework and to the$promise-\mathcal{BPP}\ = promise-\mathcal{P}$conjecture. Classical results rely on non-uniform hardness assumptions to construct derandomization algorithms that work in the worst-case, or rely on uniform hardness assumptions to construct derandomization algorithms that work only in the average-case. In both types of results, the derandomization algorithm is “black-box” and uses the standard PRG approach. In this work we present results that closely relate new and natural uniform hardness assumptions to worst-case derandomization of$promise-\mathcal{BPP}$, where the algorithms underlying the latter derandomization are non-black-box. In our main result, we show that$promise-\mathcal{BPP}\ = promise-\mathcal{P}$if the following holds: There exists a multi-output function computable by logspace-uniform circuits of polynomial size and depth$n^{2}$that cannot be computed by uniform probabilistic algorithms in time$n^{c}$, for some universal constant$c > 1$, on almost all inputs. The required failure on “almost all inputs” is stronger than the standard requirement of failing on one input of each length; however, the same assumption without the depth restriction on$f$is necessary for the conclusion. This suggests a potential equivalence between worst-case derandomization of$promise-\mathcal{BPP}$of any form (i.e., not necessarily by a black-box algorithm) and the existence of efficiently-computable functions that are hard for probabilistic algorithms on almost all inputs. In our second result, we introduce a new and uniform hardness-to-randomness tradeoff for the setting of superfast average-case derandomization: prior to this work, superfast average-case derandomization was known only under non-uniform hardness assumptions. In an extreme instantiation of our new tradeoff, under appealing uniform hardness assumptions, we show that for every polynomial$T(n)$and constant$\epsilon > 0$it holds that$\mathcal{BPTIME}[T]\subseteq \mathrm{heur}-\mathcal{DTIME}[T\cdot n^{\epsilon}]$, where the “heur” prefix means that no polynomial-time algorithm can find, with non-negligible probability, an input on which the deterministic simulation errs. Technically, our approach is to design targeted PRGs and HSGs, as introduced by Goldreich (LNCS, 2011). The targeted PRGs/HSGs “produce randomness from the input”, as sug-gested by Goldreich and Wigderson (RANDOM 2002); and their analysis relies on non-black-box versions of the reconstruction procedure of Impagliazzo and Wigderson (FOCS 1998). Our main reconstruction procedure crucially relies on the ideas underlying the proof system of Goldwasser, Kalai, and Rothblum (J. ACM 2015).

For a directed graph G with n vertices and a start vertex u_start, we wish to (approximately) sample an L-step random walk over G starting from u_start with minimum space using an algorithm that only makes few passes over the edges of the graph. This problem found many applications, for instance, in approximating the PageRank of a webpage. If only a single pass is allowed, the space complexity of this problem was shown to be Θ̃(n ⋅ L). Prior to our work, a better space complexity was only known with Õ(√L) passes. We essentially settle the space complexity of this random walk simulation problem for two-pass streaming algorithms, showing that it is Θ̃(n ⋅ √L), by giving almost matching upper and lower bounds. Our lower bound argument extends to every constant number of passes p, and shows that any p-pass algorithm for this problem uses Ω̃(n ⋅ L^{1/p}) space. In addition, we show a similar Θ̃(n ⋅ √L) bound on the space complexity of any algorithm (with any number of passes) for the related problem of sampling an L-step random walk from every vertex in the graph.

We develop a general framework that characterizes strong average-case lower bounds against circuit classes 𝒞 contained in NC¹, such as AC⁰[⊕] and ACC⁰. We apply this framework to show: - Generic seed reduction: Pseudorandom generators (PRGs) against 𝒞 of seed length ≤ n -1 and error ε(n) = n^{-ω(1)} can be converted into PRGs of sub-polynomial seed length. - Hardness under natural distributions: If 𝖤 (deterministic exponential time) is average-case hard against 𝒞 under some distribution, then 𝖤 is average-case hard against 𝒞 under the uniform distribution. - Equivalence between worst-case and average-case hardness: Worst-case lower bounds against MAJ∘𝒞 for problems in 𝖤 are equivalent to strong average-case lower bounds against 𝒞. This can be seen as a certain converse to the Discriminator Lemma [Hajnal et al., JCSS'93]. These results were not known to hold for circuit classes that do not compute majority. Additionally, we prove that classical and recent approaches to worst-case lower bounds against ACC⁰ via communication lower bounds for NOF multi-party protocols [Håstad and Goldmann, CC'91; Razborov and Wigderson, IPL'93] and Torus polynomials degree lower bounds [Bhrushundi et al., ITCS'19] also imply strong average-case hardness against ACC⁰ under the uniform distribution. Crucial to these results is the use of non-black-box hardness amplification techniques and the interplay between Majority (MAJ) and Approximate Linear Sum (SUM̃) gates. Roughly speaking, while a MAJ gate outputs 1 when the sum of the m input bits is at least m/2, a SUM̃ gate computes a real-valued bounded weighted sum of the input bits and outputs 1 (resp. 0) if the sum is close to 1 (resp. close to 0), with the promise that one of the two cases always holds. As part of our framework, we explore ideas introduced in [Chen and Ren, STOC'20] to show that, for the purpose of proving lower bounds, a top layer MAJ gate is equivalent to a (weaker) SUM̃ gate. Motivated by this result, we extend the algorithmic method and establish stronger lower bounds against bounded-depth circuits with layers of MAJ and SUM̃ gates. Among them, we prove that: - Lower bound: NQP does not admit fixed quasi-polynomial size MAJ∘SUM̃∘ACC⁰∘THR circuits. This is the first explicit lower bound against circuits with distinct layers of MAJ, SUM̃, and THR gates. Consequently, if the aforementioned equivalence between MAJ and SUM̃ as a top gate can be extended to intermediate layers, long sought-after lower bounds against the class THR∘THR of depth-2 polynomial-size threshold circuits would follow.

We study the setup where each of n users holds an element from a discrete set, and the goal is to count the number of distinct elements across all users, under the constraint of (ε,δ)-differentially privacy: - In the non-interactive local setting, we prove that the additive error of any protocol is Ω(n) for any constant ε and for any δ inverse polynomial in n. - In the single-message shuffle setting, we prove a lower bound of Ω̃(n) on the error for any constant ε and for some δ inverse quasi-polynomial in n. We do so by building on the moment-matching method from the literature on distribution estimation. - In the multi-message shuffle setting, we give a protocol with at most one message per user in expectation and with an error of Õ(√n) for any constant ε and for any δ inverse polynomial in n. Our protocol is also robustly shuffle private, and our error of √n matches a known lower bound for such protocols. Our proof technique relies on a new notion, that we call dominated protocols, and which can also be used to obtain the first non-trivial lower bounds against multi-message shuffle protocols for the well-studied problems of selection and learning parity. Our first lower bound for estimating the number of distinct elements provides the first ω(√n) separation between global sensitivity and error in local differential privacy, thus answering an open question of Vadhan (2017). We also provide a simple construction that gives Ω̃(n) separation between global sensitivity and error in two-party differential privacy, thereby answering an open question of McGregor et al. (2011).

We give an almost quadratic n2−o(1) lower bound on the space consumption of any o(√logn)-pass streaming algorithm solving the (directed) s-t reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including maximum matching, shortest path, matrix rank, and linear programming.

In this work we prove that there is a function f ∈ E NP such that, for every sufficiently large n and d = √n/logn, fn (f restricted to n-bit inputs) cannot be (1/2 + 2−d)-approximated by F2-polynomials of degree d. We also observe that a minor improvement (e.g., improving d to n1/2+ε for any ε > 0) over our result would imply E NP cannot be computed by depth-3 AC0-circuits of 2n1/2 + ε size, which is a notoriously hard open question in complexity theory.

Extending the classical “hardness-to-randomness” line-of-works, Doron, Moshkovitz, Oh, and Zuckerman (FOCS 2020) recently proved that derandomization with near-quadratic time overhead is possible, under the assumption that there exists a function in DTIME[2n] that cannot be computed by randomized SVN circuits of size 2(1−є)· n for a small є.

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether NEXP is contained in i.o.-NP; that is, it is open whether nondeterministic exponential time computation can be simulated on infinitely many input lengths by an NP algorithm. This difficulty also applies to Williams' algorithmic method for circuit lower bounds [Williams, J. ACM 2014]. [Murray and Williams, STOC 2018] proved that nondeterminstic quasi-polynomial time is not contained in ACC^0, while it remained an open problem to show that E^NP (2^O(n) time with an NP oracle) is not contained in i.o.-ACC^0. In this paper, we show how many infinitely-often circuit lower bounds proved by the algorithmic method can be adapted to establish almost-everywhere lower bounds. First, we show there is a function f in E^NP such that, for all sufficiently large input lengths n, f cannot be (1/2+exp(-n∧e))-approximated by exp(n^e)-size ACC^0 circuits on inputs of length n (for all small e), improving lower bounds in [Chen and Ren, STOC 2020] and [Viola, ECCC 2020]. Second, we construct rigid matrices in P^NP for all but finitely many inputs, rather than infinitely often as in [Alman and Chen, FOCS 2019] and [Bhangale et al. 2020]. Third, we show there is a positive c such that E^NP has constant-error probabilistic degree at least cn/(log^2 n) for all large enough n, improving an infinitely-often separation by [Viola, ECCC 2020]. Our key to proving almost-everywhere worst-case lower bounds is a new “constructive” proof of an NTIME hierarchy theorem proved by [Fortnow and Santhanam, CCC 2016], where we show for every “weak” nondeterminstic algorithm, a “refuter algorithm” exists that can construct “bad” inputs for the hard language. We use this refuter algorithm to construct an almost-everywhere hard function. To extend our lower bounds to the average case, we prove a new XOR Lemma based on approximate linear sums, and combine it with PCP of proximity ideas developed in [Chen and Williams, CCC 2019] and [Chen and Ren, STOC 2020]. As a byproduct of our new XOR Lemma, we obtain a nondeterministic pseudorandom generator for poly-size ACC^0 circuits with seed length polylog(n), which resolves an open question in [Chen and Ren, STOC 2020].

The Exponential-Time Hypothesis (ETH) is a strengthening of the P ≠ NP conjecture, stating that 3-SAT on n variables cannot be solved in (uniform) time 2ε·n, for some . In recent years, analogous hypotheses that are “exponentially-strong” forms of other classical complexity conjectures (such as NP ⊄ eq BPP or coNP ⊄ eq NP) have also been introduced, and have become widely influential. In this work, we focus on the interaction of exponential-time hypotheses with the fundamental and closely-related questions of derandomization and circuit lower bounds. We show that even relatively-mild variants of exponential-time hypotheses have far-reaching implications to derandomization, circuit lower bounds, and the connections between the two. Specifically, we prove that: 1) The Randomized Exponential-Time Hypothesis (rETH) implies that BPP can be simulated on “average-case” in deterministic (nearly-)polynomial-time (i.e., in time 2~O(log(n))=nloglog(n)O(1)). The derandomization relies on a conditional construction of a pseudorandom generator with near-exponential stretch (i.e., with seed length ~O(log(n))); this significantly improves the state-of-the-art in uniform “hardness-to-randomness” results, which previously only yielded pseudorandom generators with sub-exponential stretch from such hypotheses. 2) The Non-Deterministic Exponential-Time Hypothesis (NETH) implies that derandomization of BPP is completely equivalent to circuit lower bounds against E, and in particular that pseudorandom generators are necessary for derandomization. In fact, we show that the foregoing equivalence follows from a very weak version of NETH, and we also show that this very weak version is necessary to prove a slightly stronger conclusion that we deduce from it. Lastly, we show that disproving certain exponential-time hypotheses requires proving breakthrough circuit lower bounds. In particular, if CireuitSAT for circuits over n bits of size poly(n) can be solved by probabilistic algorithms in time 2n/polylog(n), then BPε does not have circuits of quasilinear size.

Hardness magnification reduces major complexity separations (such as EXP ⊈ NC^1) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [Igor Carboni Oliveira and Rahul Santhanam, 2018; Dylan M. McKay et al., 2019; Lijie Chen and Roei Tell, 2019; Igor Carboni Oliveira et al., 2019; Lijie Chen et al., 2019; Igor Carboni Oliveira, 2019; Lijie Chen et al., 2019] have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier than Q, while Q itself is susceptible to lower bounds but these are not yet sufficient for magnification. In this work, we provide more examples of this phenomenon, and investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program: - Does hardness magnification avoid the natural proofs barrier of Razborov and Rudich [Alexander A. Razborov and Steven Rudich, 1997]? - Can we adapt known lower bound techniques to establish the desired lower bound for Q? We establish that some instantiations of hardness magnification overcome the natural proofs barrier in the following sense: slightly superlinear-size circuit lower bounds for certain versions of the minimum circuit size problem MCSP imply the non-existence of natural proofs. As a corollary of our result, we show that certain magnification theorems not only imply strong worst-case circuit lower bounds but also rule out the existence of efficient learning algorithms. Hardness magnification might sidestep natural proofs, but we identify a source of difficulty when trying to adapt existing lower bound techniques to prove strong lower bounds via magnification. This is captured by a locality barrier: existing magnification theorems unconditionally show that the problems Q considered above admit highly efficient circuits extended with small fan-in oracle gates, while lower bound techniques against weak circuit models quite often easily extend to circuits containing such oracles. This explains why direct adaptations of certain lower bounds are unlikely to yield strong complexity separations via hardness magnification.

We establish several “sharp threshold” results for computational complexity. For certain tasks, we can prove a resource lower bound of n c for c ≥ 1 (or obtain an efficient circuit-analysis algorithm for n c size), there is strong intuition that a similar result can be proved for larger functions of n, yet we can also prove that replacing “n c ” with “n c+ε” in our results, for any ε > 0, would imply a breakthrough n ω(1) lower bound. We first establish such a result for Hardness Magnification. We prove (among other results) that for some c, the Minimum Circuit Size Problem for (logn) c -size circuits on length-n truth tables (MCSP[(logn) c ]) does not have n 2−o(1)-size probabilistic formulas. We also prove that an n 2+ε lower bound for MCSP[(logn) c ] (for any ε > 0 and c ≥ 1) would imply major lower bound results, such as NP does not have n k -size formulas for all k, and #SAT does not have log-depth circuits. Similar results hold for time-bounded Kolmogorov complexity. Note that cubic size lower bounds are known for probabilistic De Morgan formulas (for other functions). Next we show a sharp threshold for Quantified Derandomization (QD) of probabilistic formulas: (a) For all α, ε > 0, there is a deterministic polynomial-time algorithm that finds satisfying assignments to every probabilistic formula of n 2−2α−ε size with at most 2 n α falsifying assignments. (b) If for some α, ε > 0, there is such an algorithm for probabilistic formulas of n 2−α+ε-size and 2 n α unsatisfying assignments, then a full derandomization of NC 1 follows: a deterministic poly-time algorithm additively approximating the acceptance probability of any polynomial-size formula. Consequently, NP does not have n k -size formulas, for all k. Finally we show a sharp threshold result for Explicit Obstructions, inspired by Mulmuley’s notion of explicit obstructions from GCT. An explicit obstruction against S(n)-size formulas is a poly-time algorithm A such that A(1 n ) outputs a list {(x i ,f(x i ))} i ∈ [poly(n)] ⊆ {0,1} n × {0,1}, and every S(n)-size formula F is inconsistent with the (partially defined) function f. We prove that for all ε > 0, there is an explicit obstruction against n 2−ε-size formulas, and prove that there is an explicit obstruction against n 2+ε-size formulas for some ε > 0 if and only if there is an explicit obstruction against all polynomial-size formulas. This in turn is equivalent to the statement that E does not have 2 o(n)-size formulas, a breakthrough in circuit complexity.

We prove that for all constants a, NQP = NTIME[n polylog(n)] cannot be (1/2 + 2−log a n )-approximated by 2log a n -size ACC 0 ∘ THR circuits ( ACC 0 circuits with a bottom layer of THR gates). Previously, it was even open whether E NP can be (1/2+1/√n)-approximated by AC 0[⊕] circuits. As a straightforward application, we obtain an infinitely often ( NE ∩ coNE)/1-computable pseudorandom generator for poly-size ACC 0 circuits with seed length 2logє n , for all є > 0.

A frontier open problem in circuit complexity is to prove P^{NP} is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P_{/poly}. Previously, for several classes containing P^{NP}, including NP^{NP}, ZPP^{NP}, and S_2 P, such lower bounds have been proved via Karp-Lipton-style Theorems: to prove C is not in SIZE[n^k] for all k, we show that C subset P_{/poly} implies a "collapse" D = C for some larger class D, where we already know D is not in SIZE[n^k] for all k. It seems obvious that one could take a different approach to prove circuit lower bounds for P^{NP} that does not require proving any Karp-Lipton-style theorems along the way. We show this intuition is wrong: (weak) Karp-Lipton-style theorems for P^{NP} are equivalent to fixed-polynomial size circuit lower bounds for P^{NP}. That is, P^{NP} is not in SIZE[n^k] for all k if and only if (NP subset P_{/poly} implies PH subset i.o.- P^{NP}_{/n}). Next, we present new consequences of the assumption NP subset P_{/poly}, towards proving similar results for NP circuit lower bounds. We show that under the assumption, fixed-polynomial circuit lower bounds for NP, nondeterministic polynomial-time derandomizations, and various fixed-polynomial time simulations of NP are all equivalent. Applying this equivalence, we show that circuit lower bounds for NP imply better Karp-Lipton collapses. That is, if NP is not in SIZE[n^k] for all k, then for all C in {Parity-P, PP, PSPACE, EXP}, C subset P_{/poly} implies C subset i.o.-NP_{/n^epsilon} for all epsilon > 0. Note that unconditionally, the collapses are only to MA and not NP. We also explore consequences of circuit lower bounds for a sparse language in NP. Among other results, we show if a polynomially-sparse NP language does not have n^{1+epsilon}-size circuits, then MA subset i.o.-NP_{/O(log n)}, MA subset i.o.-P^{NP[O(log n)]}, and NEXP is not in SIZE[2^{o(m)}]. Finally, we observe connections between these results and the "hardness magnification" phenomena described in recent works.

We considerably sharpen the known connections between circuit-analysis algorithms and circuit lower bounds, show intriguing equivalences between the analysis of weak circuits and (apparently difficult) circuits, and provide strong new lower bounds for approximately computing Boolean functions with depth-two neural networks and related models. - We develop approaches to proving THR o THR lower bounds (a notorious open problem), by connecting algorithmic analysis of THR o THR to the provably weaker circuit classes THR o MAJ and MAJ o MAJ, where exponential lower bounds have long been known. More precisely, we show equivalences between algorithmic analysis of THR o THR and these weaker classes. The epsilon-error CAPP problem asks to approximate the acceptance probability of a given circuit to within additive error epsilon; it is the "canonical" derandomization problem. We show: - There is a non-trivial (2^n/n^{omega(1)} time) 1/poly(n)-error CAPP algorithm for poly(n)-size THR o THR circuits if and only if there is such an algorithm for poly(n)-size MAJ o MAJ. - There is a delta > 0 and a non-trivial SAT (delta-error CAPP) algorithm for poly(n)-size THR o THR circuits if and only if there is such an algorithm for poly(n)-size THR o MAJ. Similar results hold for depth-d linear threshold circuits and depth-d MAJORITY circuits. These equivalences are proved via new simulations of THR circuits by circuits with MAJ gates. - We strengthen the connection between non-trivial derandomization (non-trivial CAPP algorithms) for a circuit class C, and circuit lower bounds against C. Previously, [Ben-Sasson and Viola, ICALP 2014] (following [Williams, STOC 2010]) showed that for any polynomial-size class C closed under projections, non-trivial (2^{n}/n^{omega(1)} time) CAPP for OR_{poly(n)} o AND_{3} o C yields NEXP does not have C circuits. We apply Probabilistic Checkable Proofs of Proximity in a new way to show it would suffice to have a non-trivial CAPP algorithm for either XOR_2 o C, AND_2 o C or OR_2 o C. - A direct corollary of the first two bullets is that NEXP does not have THR o THR circuits would follow from either: - a non-trivial delta-error CAPP (or SAT) algorithm for poly(n)-size THR o MAJ circuits, or - a non-trivial 1/poly(n)-error CAPP algorithm for poly(n)-size MAJ o MAJ circuits. - Applying the above machinery, we extend lower bounds for depth-two neural networks and related models [R. Williams, CCC 2018] to weak approximate computations of Boolean functions. For example, for arbitrarily small epsilon > 0, we prove there are Boolean functions f computable in nondeterministic n^{log n} time such that (for infinitely many n) every polynomial-size depth-two neural network N on n inputs (with sign or ReLU activation) must satisfy max_{x in {0,1}^n}|N(x)-f(x)|>1/2-epsilon. That is, short linear combinations of ReLU gates fail miserably at computing f to within close precision. Similar results are proved for linear combinations of ACC o THR circuits, and linear combinations of low-degree F_p polynomials. These results constitute further progress towards THR o THR lower bounds.

For a matrix H over a field F, its rank-r rigidity, denoted R_H (r), is the minimum Hamming distance from H to a matrix of rank at most r over F. A central open challenge in complexity theory is to give explicit constructions of rigid matrices for a variety of parameter settings. In this work, building on Williams' seminal connection between circuit-analysis algorithms and lower bounds [Williams, J. ACM 2014], we give a construction of rigid matrices in P^NP. Letting q = p^r be a prime power, we show: • There is an absolute constant δ>0 such that, for all constants ε >0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs a matrix H_N ∊ {0,1}^N×N with R_H_N (2^ (log N)^ 1/4-ε) ≥ δ ⋅ N^2 over F_q. Using known connections between matrix rigidity and other topics in complexity theory, we derive several consequences of our constructions, including: • There is a function f ∊ TIME [2^ (log n)^ ω(1)]^ NP such that f ∉ PH^cc. Previously, it was open whether E^NP ⊂ PH^cc. • For all ε >0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs an N × N matrix H_N ∊ {0,1}^N×N whose linear transformation requires depth-2 F_q-linear circuits of size Ω(N ⋅ 2^ (log N)^ 1/4 - ε). The previous best lower bound for an explicit family of N × N matrices over F_q was only Ω(N log^2 N / (log log N)^2), for asymptotically good error-correcting codes.

Following the seminal work of [Williams, J. ACM 2014], in a recent breakthrough, [Murray and Williams, STOC 2018] proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC0circuits. We strengthen the above lower bound to an average case one, by proving that for all constants c, there is a language in NQP, which is not 1/2+1/logc(n)-approximable by polynomial-size ACC0circuits. In fact, our lower bound holds for a larger circuit class: 2(logan)-size ACC0circuits with a layer of threshold gates at the bottom (ACC ο THR circuits), for all constants a. Our work also improves the average-case lower bound for NEXP against polynomial-size ACC circuits by [Chen, Oliveira, and Santhanam, LATIN 2018]. Our new lower bound builds on several interesting components, including: : Barrington's theorem and the existence of an NC1-complete language which is random self-reducible. : The sub-exponential witness-size lower bound for NE against ACC0and the conditional non-deterministic PRG construction in [Williams, SICOMP 2016]. : An “almost'' almost-everywhere MA average-case lower bound (which strengthens the corresponding worst-case lower bound in [Murray and Williams, STOC 2018]). A PSPACE-complete language which is same-length checkable, error-correctable and also has some other nice reducibility properties, which builds on [Trevisan and Vadhan, Computational Complexity 2007]. Moreover, all its reducibility properties have corresponding low-depth non-adaptive oracle circuits. Like other lower bounds proved via the "algorithmic approach'', the only property of ACC0ο THR exploited by us is the existence of a non-trivial SAT algorithm for ACC0ο THR [Williams, STOC 2014]. Therefore, for any typical circuit class ℓ, our results apply to them as well if the corresponding non-trivial SAT (in fact, GAP-UNSAT) algorithms are discovered.

In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of computing time-bounded Kolmogorov complexity. In [Oliveira and Santhanam, FOCS 2018], [Oliveira, Pich, and Santhanam, CCC 2019], and [McKay, Murray, and Williams, STOC 2019], it was shown that minor (n1+ε-style) lower bounds for MCSP[2o(m)] or MKtP[2o(m)] would imply breakthrough circuit lower bounds such as NP⊄P/poly, NP⊄NC1, or EXP⊄P/poly. We consider the question: What is so special about MCSP and MKtP? Why do they admit this striking phenomenon? One simple property is that all variants of MCSP (and MKtP) considered in prior work are sparse languages. For example, MCSP[s(m)] has 2Õ(s(m))yes-instances of length n = 2m, so MCSP[2o(m)] is 2no(1)-sparse. We show that there is a hardness magnification phenomenon for all equally-sparse NP languages. Formally, suppose there is an ε > 0 and a language L ∈ NP which is 2no(1)-sparse, and L ∈/ Circuit[n1+ε]. Then NP does not have nk-size circuits for all k. We prove analogous theorems for De Morgan formulas, B2-formulas, branching programs, AC0[6] and TC0circuits, and more: improving the state of the art in NP lower bounds against any of these models by an ε factor in the exponent would already imply NP lower bounds for all fixed polynomials. In fact, in our proofs it is not necessary to prove a (say) n1+εcircuit size lower bound for L: one only has to prove a lower bound against n1+ε-time nε-space deterministic algorithms with nεadvice bits. Such lower bounds are well-known for non-sparse problems. Building on our techniques, we also show interesting new hardness magnifications for search-MCSP and search-MKtP (where one must output small circuits or short representations of strings), showing consequences such as ⊕P (or PP, PSPACE, and EXP) is not contained in P/poly (or NC1, AC0[6], or branching programs of polynomial size). For instance, if there is an ε > 0 such that search-MCSP[2βm] does not have De Morgan formulas of size n3+εfor all constants ß > 0, then ⊕P⊄NC1.

In recent years, the polynomial method from circuit complexity has been applied to several fundamental problems and obtains the state-of-the-art running times (e.g., R. Williams's n^3 / 2^{Omega(sqrt{log n})} time algorithm for APSP). As observed in [Alman and Williams, STOC 2017], almost all applications of the polynomial method in algorithm design ultimately rely on certain (probabilistic) low-rank decompositions of the computation matrices corresponding to key subroutines. They suggest that making use of low-rank decompositions directly could lead to more powerful algorithms, as the polynomial method is just one way to derive such a decomposition. Inspired by their observation, in this paper, we study another way of systematically constructing low-rank decompositions of matrices which could be used by algorithms - communication protocols. Since their introduction, it is known that various types of communication protocols lead to certain low-rank decompositions (e.g., P protocols/rank, BQP protocols/approximate rank). These are usually interpreted as approaches for proving communication lower bounds, while in this work we explore the other direction. We have the following two generic algorithmic applications of communication protocols: - Quantum Communication Protocols and Deterministic Approximate Counting. Our first connection is that a fast BQP communication protocol for a function f implies a fast deterministic additive approximate counting algorithm for a related pair counting problem. Applying known BQP communication protocols, we get fast deterministic additive approximate counting algorithms for Count-OV (#OV), Sparse Count-OV and Formula of SYM circuits. In particular, our approximate counting algorithm for #OV runs in near-linear time for all dimensions d = o(log^2 n). Previously, even no truly-subquadratic time algorithm was known for d = omega(log n). - Arthur-Merlin Communication Protocols and Faster Satisfying-Pair Algorithms. Our second connection is that a fast AM^{cc} protocol for a function f implies a faster-than-bruteforce algorithm for f-Satisfying-Pair. Using the classical Goldwasser-Sisper AM protocols for approximating set size, we obtain a new algorithm for approximate Max-IP_{n,c log n} in time n^{2 - 1/O(log c)}, matching the state-of-the-art algorithms in [Chen, CCC 2018]. We also apply our second connection to shed some light on long-standing open problems in communication complexity. We show that if the Longest Common Subsequence (LCS) problem admits a fast (computationally efficient) AM^{cc} protocol (polylog(n) complexity), then polynomial-size Formula-SAT admits a 2^{n - n^{1-delta}} time algorithm for any constant delta > 0, which is conjectured to be unlikely by a recent work [Abboud and Bringmann, ICALP 2018]. The same holds even for a fast (computationally efficient) PH^{cc} protocol.

We develop techniques to prove lower bounds for the BCAST(log n) Broadcast Congested Clique model (a distributed message passing model where in each round, each processor can broadcast an O(log n)-sized message to all other processors). Our techniques are built to prove bounds for natural input distributions. So far, all lower bounds for problems in the model relied on constructing specifically tailored graph families for the specific problem at hand, resulting in lower bounds for artificially constructed inputs, instead of natural input distributions.

In this paper we study the fine-grained complexity of finding exact and approximate solutions to problems in P. Our main contribution is showing reductions from an exact to an approximate solution for a host of such problems. As one (notable) example, we show that the Closest-LCS-Pair problem (Given two sets of strings A and B, compute exactly the maximum LCS(a, b) with (a, b) ∊ A × B) is equivalent to its approximation version (under near-linear time reductions, and with a constant approximation factor). More generally, we identify a class of problems, which we call BP-Pair-Class, comprising both exact and approximate solutions, and show that they are all equivalent under near-linear time reductions. Exploring this class and its properties, we also show: Under the NC-SETH assumption (a significantly more relaxed assumption than SETH), solving any of the problems in this class requires essentially quadratic time. Modest improvements on the running time of known algorithms (shaving log factors) would imply that NEXP is not in non-uniform NC1. Finally, we leverage our techniques to show new barriers for deterministic approximation algorithms for LCS. A very important consequence of our results is that they continue to hold in the data structure setting. In particular, it shows that a data structure for approximate Nearest Neighbor Search for LCS (NNSLCS) implies a data structure for exact NNSLCS and a data structure for answering regular expression queries with essentially the same complexity. At the heart of these new results is a deep connection between interactive proof systems for bounded-space computations and the fine-grained complexity of exact and approximate solutions to problems in P. In particular, our results build on the proof techniques from the classical IP = PSPACE result.

The Orthogonal Vectors problem (OV) asks: given n vectors in {0, 1}O(log n), are two of them orthogonal? OV is easily solved in O(n2 log n) time, and it is a central problem in fine-grained complexity: dozens of conditional lower bounds are based on the popular hypothesis that OV cannot be solved in (say) n1.99 time. However, unlike the APSP problem, few other problems are known to be non-trivially equivalent to OV. We show OV is truly-subquadratic equivalent to several fundamental problems, all of which (a priori) look harder than OV. A partial list is given below: 1. (Min-IP/Max-IP) Find a red-blue pair of vectors with minimum (respectively, maximum) inner product, among n vectors in {0, 1}O(log n). 2. (Exact-IP) Find a red-blue pair of vectors with inner product equal to a given target integer, among n vectors in {0, 1}O(log n). 3. (Apx-Min-IP/Apx-Max-IP) Find a red-blue pair of vectors that is a 100-approximation to the minimum (resp. maximum) inner product, among n vectors in {0, l}O(log n). 4. (Approximate Bichrom.-ℓp-Closest-Pair) Compute a (1+ Ω(1))-approximation to the ℓp-closest red-blue pair (for a constant p ∊ [1, 2]), among n points in ℝ, d ≤ no(1). 5. (Approximate ℓp-Furthest-Pair) Compute a (1 + Ω(1))-approximation to the ℓp-furthest pair (for a constant p ∊ [1, 2]), among n points in ℝ, d ≤ no(1). Therefore, quick constant-factor approximations to maximum inner product imply quick exact solutions to maximum inner product, in the O(log n)-dimensional setting. Another consequence is that the ability to find vectors with zero inner product suffices for finding vectors with maximum inner product. Our equivalence results are robust enough that they continue to hold in the data structure setting. In particular, we show that there is a poly(n) space, n1–ε query time data structure for Partial Match with vectors from {0, 1}O(log n) if and only if such a data structure exists for 1 + Ω(1) Approximate Nearest Neighbor Search in Euclidean space. To establish the equivalences, we introduce two general frameworks for reductions to OV: one based on ∑2 communication protocols, and another based on locality-sensitive hashing families. In addition, we obtain an n2–1/O(log c) time algorithm for Apx-Min-IP with n vectors from {0, 1}c log n, matching state-of-the-art algorithms for OV and Apx-Max-IP. As an application, we obtain a faster algorithm for approximating “almost solvable” MAX-SAT instances.

The best known lower bounds for the circuit class TC0 are only slightly super-linear. Similarly, the best known algorithm for derandomization of this class is an algorithm for quantified derandomization (i.e., a weak type of derandomization) of circuits of slightly super-linear size. In this paper we show that even very mild quantitative improvements of either of the two foregoing results would already imply super-polynomial lower bounds for TC0. Specifically:

In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets $A$ and $B$ of vectors, and the goal is to find $a \in A$ and $b \in B$ maximizing inner product $a \cdot b$. Max-IP is very basic and serves as the base problem in the recent breakthrough of [Abboud et al., FOCS 2017] on hardness of approximation for polynomial-time problems. It is also used (implicitly) in the argument for hardness of exact $\ell_2$-Furthest Pair (and other important problems in computational geometry) in poly-log-log dimensions in [Williams, SODA 2018]. We have three main results regarding this problem. First, we study the best multiplicative approximation ratio for Boolean Max-IP in sub-quadratic time. We show that, for Max-IP with two sets of $n$ vectors from $\{0,1\}^{d}$, there is an $n^{2 - Ω(1)}$ time $\left( d/\log n \right)^{Ω(1)}$-multiplicative-approximating algorithm, and we show this is conditionally optimal, as such a $\left(d/\log n\right)^{o(1)}$-approximating algorithm would refute SETH. Second, we achieve a similar characterization for the best additive approximation error to Boolean Max-IP. We show that, for Max-IP with two sets of $n$ vectors from $\{0,1\}^{d}$, there is an $n^{2 - Ω(1)}$ time $Ω(d)$-additive-approximating algorithm, and this is conditionally optimal, as such an $o(d)$-approximating algorithm would refute SETH [Rubinstein, STOC 2018]. Last, we revisit the hardness of solving Max-IP exactly for vectors with integer entries. We show that, under SETH, for Max-IP with sets of $n$ vectors from $\mathbb{Z}^{d}$ for some $d = 2^{O(\log^{*} n)}$, every exact algorithm requires $n^{2 - o(1)}$ time. With the reduction from [Williams, SODA 2018], it follows that $\ell_2$-Furthest Pair and Bichromatic $\ell_2$-Closest Pair in $2^{O(\log^{*} n)}$ dimensions require $n^{2 - o(1)}$ time.

Bounded rationality aims to understand the effects of how limited rationality affects decision-making. The traditional models in game theory and multiagent system research, such as finite automata or unrestricted Turing machine, fall short of capturing how intelligent agents make decision in realistic applications. To address this problem, we model bounded rational agents as restricted Turing machines: restrictions on running time and on storage space. We study our model under the context of two-person repeated games. In the case where the running time of Turing machines is restricted, we show that computing the best response of a given strategy is much harder than the strategy itself. In the case where the storage space of the Turing machines is restricted, we show the best response of a space restricted strategy can not be implemented by machines within the same size (up to a constant factor). Finally, we study how these restrictions affect the set of Nash equilibria in infinitely repeated games.We show restricting the agent’s computational resources will give rise to new Nash equilibria.

In the Best-k-Arm problem, we are given n stochastic bandit arms, each associated with an unknown reward distribution. We are required to identify the k arms with the largest means by taking as few samples as possible. In this paper, we make progress towards a complete characterization of the instance-wise sample complexity bounds for the Best-k-Arm problem. On the lower bound side, we obtain a novel complexity term to measure the sample complexity that every Best-k-Arm instance requires. This is derived by an interesting and nontrivial reduction from the Best-1-Arm problem. We also provide an elimination-based algorithm that matches the instance-wise lower bound within doubly-logarithmic factors. The sample complexity of our algorithm strictly dominates the state-of-the-art for Best-k-Arm (module constant factors).

We study the combinatorial pure exploration problem \textscBest-Set in a stochastic multi-armed bandit game. In an \textscBest-Set instance, we are given $n$ stochastic arms with unknown reward distributions, as well as a family $\mathcal{F}$ of feasible subsets over the arms. Let the weight of an arm be the mean of its reward distribution. Our goal is to identify the feasible subset in $\mathcal{F}$ with the maximum total weight, using as few samples as possible. The problem generalizes the classical best arm identification problem and the top-$k$ arm identification problem, both of which have attracted significant attention in recent years. We provide a novel \textitinstance-wise lower bound for the sample complexity of the problem, as well as a nontrivial sampling algorithm, matching the lower bound up to a factor of $\ln|\mathcal{F}|$. For an important class of combinatorial families (including spanning trees, matchings, and path constraints), we also provide polynomial time implementation of the sampling algorithm, using the equivalence of separation and optimization for convex program, and the notion of approximate Pareto curves in multi-objective optimization (note that $|\mathcal{F}|$ can be exponential in $n$). We also show that the $\ln|\mathcal{F}|$ factor is inevitable in general, through a nontrivial lower bound construction utilizing a combinatorial structure resembling the Nisan-Wigderson design. Our results significantly improve several previous results for several important combinatorial constraints, and provide a tighter understanding of the general \textscBest-Set problem. We further introduce an even more general problem, formulated in geometric terms. We are given $n$ Gaussian arms with unknown means and unit variance. Consider the $n$-dimensional Euclidean space $\mathbb{R}^n$, and a collection $\mathcal{O}$ of disjoint subsets. Our goal is to determine the subset in $\mathcal{O}$ that contains the mean profile (which is the $n$-dimensional vector of the means), using as few samples as possible. The problem generalizes most pure exploration bandit problems studied in the literature. We provide the first nearly optimal sample complexity upper and lower bounds for the problem.

In the classical best arm identification (Best-$1$-Arm) problem, we are given $n$ stochastic bandit arms, each associated with a reward distribution with an unknown mean. Upon each play of an arm, we can get a reward sampled i.i.d. from its reward distribution. We would like to identify the arm with the largest mean with probability at least $1-δ$, using as few samples as possible. The problem has a long history and understanding its sample complexity has attracted significant attention since the last decade. However, the optimal sample complexity of the problem is still unknown. Recently, Chen and Li (2016) made an interesting conjecture, called gap-entropy conjecture, concerning the instance optimal sample complexity of Best-$1$-Arm. Given a Best-$1$-Arm instance $I$ (i.e., a set of arms), let $\mu_[i]$ denote the $i$th largest mean and $\Delta_[i]=\mu_[1]-\mu_[i]$ denote the corresponding gap. $H(I)=\sum_i=2^n\Delta_[i]^-2$ denotes the complexity of the instance. The gap-entropy conjecture states that for any instance $I$, $Ω\left(H(I)⋅\left(\lnδ^-1 + \mathsf{Ent}(I)\right)\right)$ is an instance lower bound, where $\mathsf{Ent}(I)$ is an entropy-like term determined by the gaps, and there is a $δ$-correct algorithm for Best-$1$-Arm with sample complexity $O\left(H(I)⋅\left(\lnδ^-1 + \mathsf{Ent}(I)\right)+\Delta_[2]^-2\ln\ln\Delta_[2]^-1\right)$. We note that $Θ\left(\Delta_[2]^-2\ln\ln\Delta_[2]^-1\right)$ is necessary and sufficient to solve the two-arm instance with the best and second best arms. If the conjecture is true, we would have a complete understanding of the instance-wise sample complexity of Best-$1$-Arm (up to constant factors). In this paper, we make significant progress towards a complete resolution of the gap-entropy conjecture. For the upper bound, we provide a highly nontrivial algorithm which requires \[O\left(H(I)⋅\left(\lnδ^-1 + \mathsf{Ent}(I)\right)+\Delta_[2]^-2\ln\ln\Delta_[2]^-1\mathrmpolylog(n,δ^-1)\right)\]samples in expectation for any instance $I$. For the lower bound, we show that for any Gaussian Best-$1$-Arm instance with gaps of the form $2^-k$, any $δ$-correct monotone algorithm requires at least \[Ω\left(H(I)⋅\left(\lnδ^-1 + \mathsf{Ent}(I)\right)\right)\]samples in expectation. Here, a monotone algorithm is one which uses no more samples (in expectation) on $I’$ than on $I$, if $I’$ is a sub-instance of $I$ obtained by removing some sub-optimal arms.

We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZK contains hard problems, by exhibiting an oracle relative to which SZK (indeed, even NISZK) is not contained in the class UPP, containing those problems solvable by randomized algorithms with unbounded error. This answers an open question of Watrous from 2002. Second, we “lift” this oracle separation to the setting of communication complexity, thereby answering a question of Goos et al. (ICALP 2016). Third, we give relativized evidence that perfect zero knowledge proofs (captured by the class PZK) are weaker than general zero knowledge proofs. Specifically, we exhibit oracles which separate SZK from PZK, NISZK from NIPZK and PZK from coPZK. The first of these results answers a question raised in 1991 by Aiello and Hastad (Information and Computation), and the second answers a question of Lovett and Zhang (2016). We also describe additional applications of these results outside of structural complexity. The technical core of our results is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree.

We study the pure exploration problem subject to a matroid constraint (Best-Basis) in a stochastic multi-armed bandit game. In a Best-Basis instance, we are given n stochastic arms with unknown reward distributions, as well as a matroid \mathcalM over the arms. Let the weight of an arm be the mean of its reward distribution. Our goal is to identify a basis of \mathcalM with the maximum total weight, using as few samples as possible. The problem is a significant generalization of the best arm identification problem and the top-k arm identification problem, which have attracted significant attentions in recent years. We study both the exact and PAC versions of Best-Basis, and provide algorithms with nearly-optimal sample complexities for these versions. Our results generalize and/or improve on several previous results for the top-k arm identification problem and the combinatorial pure exploration problem when the combinatorial constraint is a matroid.

The best arm identification problem (BEST-1-ARM) is the most basic pure exploration problem in stochastic multi-armed bandits. The problem has a long history and attracted significant attention for the last decade. However, we do not yet have a complete understanding of the optimal sample complexity of the problem: The state-of-the-art algorithms achieve a sample complexity of O(\sum_i=2^n \Delta_i^-2(\lnδ^-1 + \ln\ln\Delta_i^-1)) (\Delta_i is the difference between the largest mean and the i^th mean), while the best known lower bound is Ω(\sum_i=2^n \Delta_i^-2\lnδ^-1) for general instances and Ω(∆^-2 \ln\ln ∆^-1) for the two-arm instances. We propose to study the instance-wise optimality for the BEST-1-ARM problem. Previous work has proved that it is impossible to have an instance optimal algorithm for the 2-arm problem. However, we conjecture that modulo the additive term Ω(\Delta_2^-2 \ln\ln \Delta_2^-1) (which is an upper bound and worst case lower bound for the 2-arm problem), there is an instance optimal algorithm for BEST-1-ARM. Moreover, we introduce a new quantity, called the gap entropy for a best-arm problem instance, and conjecture that it is the instance-wise lower bound. Hence, resolving this conjecture would provide a final answer to the old and basic problem.

We study the following problem: with the power of postselection (classically or quantumly), what is your ability to answer adaptive queries to certain languages? More specifically, for what kind of computational classes C, we have P^C belongs to PostBPP or PostBQP? While a complete answer to the above question seems impossible given the development of present computational complexity theory. We study the analogous question in query complexity, which sheds light on the limitation of relativized methods (the relativization barrier) to the above question. Informally, we show that, for a partial function f, if there is no efficient small bounded-error algorithm for f classically or quantumly, then there is no efficient postselection bounded-error algorithm to answer adaptive queries to f classically or quantumly. Our results imply a new proof for the classical oracle separation P^{NP^O} notsubset PP^O, which is arguably more elegant. They also lead to a new oracle separation P^{SZK^O} notsubset PP^O, which is close to an oracle separation between SZK and PP - an open problem in the field of oracle separations. Our result also implies a hardness amplification construction for polynomial approximation: given a function f on n bits, we construct an adaptive-version of f, denoted by F, on O(m·n) bits, such that if f requires large degree to approximate to error 2/3 in a certain one-sided sense, then F requires large degree to approximate even to error 1/2 - 2^{-m}. Our construction achieves the same amplification in the work of Thaler (ICALP, 2016), by composing a function with O(log n) deterministic query complexity, which is in sharp contrast to all the previous results where the composing amplifiers are all hard functions in a certain sense.