Meta-complexity investigates the complexity of computational problems and tasks that are themselves about computations and their complexity. Understanding whether such problems can capture the hardness of NP is a central research direction. A longstanding open problem in this area is to establish the NP-hardness of MINKT (Ker-I Ko, 1991 [Ker{-}I Ko, 1991]), the problem of estimating time-bounded Kolmogorov complexity. We contribute to this research direction by studying nK^t, a natural variant of Kolmogorov complexity that captures the complexity of representing a string using time-bounded nondeterministic computations [Buhrman et al., 2001]. Let MINnKT denote the task of estimating nK^t(x) of a given input string x. We prove that MINnKT ∈ BPP if and only if NP ⊆ BPP. This can be interpreted as a solution to Ko’s question in the setting of nondeterministic time-bounded Kolmogorov complexity. Crucial to the proof of this result is the investigation of a new notion of probabilistic nondeterministic time-bounded Kolmogorov complexity called pnK^t. This measure can be seen as an extension of pK^t complexity [Halley Goldberg et al., 2022] obtained by replacing 𝖪^t with nK^t. We establish unconditionally that pnK^t has nearly all key properties of (time-unbounded) Kolmogorov complexity, such as language compression, conditional coding, and a form of symmetry of information. Finally, we show that the corresponding meta-computational problem MINpnKT also captures the hardness of NP, and that extending this result to the closely related problem Gap-MINpnKT would imply the exclusion of PH-Heuristica.

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.

Symmetry of Information (SoI) is a fundamental result in Kolmogorov complexity stating that for all n-bit strings x and y, we have K(x,y) = K(y) + K(x ∣ y) up to an additive error of O(logn). In contrast, understanding whether SoI holds for time-bounded Kolmogorov complexity measures is closely related to longstanding open problems in complexity theory and cryptography, such as the P versus NP question and the existence of one-way functions.

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

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

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 introduce and study the following natural total search problem, which we call the heavy element avoidance (Heavy Avoid) problem: for a distribution on$N$bits specified by a Boolean circuit sampling it, and for some parameter$\delta(N)\geq 1/$poly$(N)$fixed in advance, output an$N$-bit string that has probability less than$\delta(N)$. We show that the complexity of Heavy Avoid is closely tied to frontier open questions in complexity theory about uniform randomized lower bounds and derandomization. Among other results, we show: 1)For a wide range of circuit classes$\mathcal{C}$, including$\text{ACC}^{0}, \text{TC}^{0},\text{NC}^{1}$and general Boolean circuits, EX P does not have uniform randomized C-circuits if and only if Heavy Avoid for uniform implicit C -samplers has efficient deterministic algorithms infinitely often. This gives the first algorithmic characterization of lower bounds for EXP against uniform randomized low-depth circuits. We show similar algorithmic characterizations for lower bounds in PSPACE, NP and$\text{EXP}^{\text{NP}}$. 2)Unconditionally, there are polynomial-time pseudodeterministic algorithms that work infinitely often for several variants of Heavy Avoid, such as for uniform samplers of small randomness complexity. In contrast, the existence of a similar algorithm that solves Heavy Avoid for arbitrary polynomial-time samplers would solve a long-standing problem about hierarchies for probabilistic time. 3)If there is a time and depth efficient deterministic algorithm for Heavy Avoid, then$BPP=P$. Without the depth-efficiency requirement in the assumption, we still obtain a non-trivial form of infinitely-often deterministic simulation of randomized algorithms. These results are shown using non-black-box reductions, and we argue that the use of non-black-box reductions is essential here. The full version is available on ECCC [1].

We study FO+, a fragment of first-order logic on finite words, where monadic predicates can only appear positively. We show that there is an FO-definable language that is monotone in monadic predicates but not definable in FO+. This provides a simple proof that Lyndon's preservation theorem fails on finite structures. We lift this example language to finite graphs, thereby providing a new result of independent interest for FO-definable graph classes: negation might be needed even when the class is closed under addition of edges. We finally show that the problem of whether a given regular language of finite words is definable in FO+ is undecidable.

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

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) established that if SoI holds for time-bounded Kolmogorov complexity then cryptographic one-way functions do not exist, and asked if a converse holds.

While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jerabek’s theory APC1 (2007) and of higher levels of Buss’s hierarchy S2i (1986) has been a more elusive task. Even in the more restricted setting of Cook’s theory PV (1975), known results often rely on a less natural formalization that encodes a complexity statement using a collection of sentences instead of a single sentence. This is done to reduce the quantifier complexity of the resulting sentences so that standard witnessing results can be invoked.

The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $δ$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/δ) + O(1)$. In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that if $x$ can be efficiently sampled with probability $δ$ then rKt$(x) = O(\log(1/δ)) + O(\log n)$, where rKt denotes the randomized analogue of Levin's Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a $O(\log(1/δ))$ bound instead of the information-theoretic optimal $\log(1/δ)$. We show a coding theorem for rKt with a factor of $2$. As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given $x$, the code of the sampler, and $δ$, it outputs, with probability $\ge 0.99$, a probabilistic representation of $x$ that certifies this rKt complexity bound. Assuming the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt$(x) \leq (2 - o(1)) \cdot \log(1/δ) +$ poly$(\log n)$. Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters. We consider pK$^t$ complexity [GKLO22], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pK$^t$, and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [AF09] which characterizes the worst-case running times of languages that are in average polynomial-time over all P-samplable distributions.

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.

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let$\mathfrak{C}$be a class of polynomial-size concepts, and suppose that$\mathfrak{C}$can be PAC-learned with membership queries under the uniform distribution with error$1/2 -\gamma$by a time$T$quantum algorithm. We prove that if$\gamma^{2}\cdot T \ll 2^{n} /n$, then$\mathsf{BQE}\not\subset \mathfrak{C}$, where$\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]$is an exponential-time analogue of$\mathsf{BQP}$. This result is optimal in both$\gamma$and$T$, since it is not hard to learn any class$\mathfrak{C}$of functions in (classical) time$T=2^{n}$(with no error), or in quantum time$T= \mathsf{poly}(n)$with error at most$1/2-\Omega(2^{-n/2})$via Fourier sampling. In other words, even a marginal quantum speedup over these generic learning algorithms would lead to major consequences in complexity lower bounds. As a consequence, our result shows that the study of quantum learning speedups is intimately connected to fundamental open problems about algorithms, quantum computing, and complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges, since extracting computational hardness from a quantum computation is inherently more complicated. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.

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

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.

A probabilistic representation of a string x ∈ {0,1}ⁿ is given by the code of a randomized algorithm that outputs x with high probability [Igor C. Oliveira, 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in time-bounded Kolmogorov complexity. More precisely, we show that if a distribution ensemble 𝒟_m can be uniformly sampled in time T(m) and generates a string x ∈ {0,1}^* with probability at least δ, then x admits a time-bounded probabilistic representation of complexity O(log(1/δ) + log (T) + log(m)). Under mild assumptions, a representation of this form can be computed from x and the code of the sampler in time polynomial in n = |x|. We derive consequences of this result relevant to the study of data compression, pseudodeterministic algorithms, time hierarchies for sampling distributions, and complexity lower bounds. In particular, we describe an instance-based search-to-decision reduction for Levin’s Kt complexity [Leonid A. Levin, 1984] and its probabilistic analogue rKt [Igor C. Oliveira, 2019]. As a consequence, if a string x admits a succinct time-bounded representation, then a near-optimal representation can be generated from x with high probability in polynomial time. This partially addresses in a time-bounded setting a question from [Leonid A. Levin, 1984] on the efficiency of computing an optimal encoding of a string.

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of BPTIME: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.

Can we design efficient algorithms for finding fast algorithms?This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications.Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an explicitly given function is NP-complete.While this is known to hold in restricted models such as DNFs, making progress with respect to more expressive classes of circuits has been elusive.In this work, we establish the first NP-hardness result for circuit minimization of total functions in the setting of general (unrestricted) Boolean circuits.More precisely, we show that computing the minimum circuit size of a given multi-output Boolean function f : {0, 1} n → {0, 1} m is NP-hard under many-one polynomial-time randomized reductions.Our argument builds on a simpler NP-hardness proof for the circuit minimization problem for (single-output) Boolean functions under an extended set of generators.Complementing these results, we investigate the computational hardness of minimizing communication.We establish that several variants of this problem are NP-hard under deterministic reductions.In particular, unless P = NP, no polynomial-time computable function can approximate the deterministic two-party communication complexity of a partial Boolean function up to a polynomial.This has consequences for the class of structural results that one might hope to show about the communication complexity of partial functions.

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

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.

Proving that there are problems in $\mathsf{P}^\mathsf{NP}$ that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere circuit lower bounds is open even for problems in $\mathsf{MAEXP}$. Giving the notorious difficulty of proving lower bounds that hold for all large input lengths, we ask the following question: Can we show that a large set of techniques cannot prove that $\mathsf{NP}$ is easy infinitely often? Motivated by this and related questions about the interaction between mathematical proofs and computations, we investigate circuit complexity from the perspective of logic. Among other results, we prove that for any parameter $k \geq 1$ it is consistent with theory $T$ that computational class ${\mathcal C} \not \subseteq \textit{i.o.}\mathrm{SIZE}(n^k)$, where $(T, \mathcal{C})$ is one of the pairs: $T = \mathsf{T}^1_2$ and ${\mathcal C} = \mathsf{P}^\mathsf{NP}$, $T = \mathsf{S}^1_2$ and ${\mathcal C} = \mathsf{NP}$, $T = \mathsf{PV}$ and ${\mathcal C} = \mathsf{P}$. In other words, these theories cannot establish infinitely often circuit upper bounds for the corresponding problems. This is of interest because the weaker theory $\mathsf{PV}$ already formalizes sophisticated arguments, such as a proof of the PCP Theorem. These consistency statements are unconditional and improve on earlier theorems of [KO17] and [BM18] on the consistency of lower bounds with $\mathsf{PV}$.

This work continues the development of hardness magnification. The latter proposes a new strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful. We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs to distinguish instances (strings or truth-tables) of complexity <= s_1(N) from instances of complexity >= s_2(N), and N = 2^n denotes the input length. In MCSP, complexity is measured by circuit size, while in MKtP one considers Levin’s notion of time-bounded Kolmogorov complexity. (In our results, the parameters s_1(N) and s_2(N) are asymptotically quite close, and the problems almost coincide with their standard formulations without a gap.) We establish that for Gap-MKtP[s_1,s_2] and Gap-MCSP[s_1,s_2], a marginal improvement over the state-of-the-art in unconditional lower bounds in a variety of computational models would imply explicit super-polynomial lower bounds. Theorem. There exists a universal constant c >= 1 for which the following hold. If there exists epsilon > 0 such that for every small enough beta > 0 (1) Gap-MCSP[2^{beta n}/c n, 2^{beta n}] !in Circuit[N^{1 + epsilon}], then NP !subseteq Circuit[poly]. (2) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in TC^0[N^{1 + epsilon}], then EXP !subseteq TC^0[poly]. (3) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in B_2-Formula[N^{2 + epsilon}], then EXP !subseteq Formula[poly]. (4) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in U_2-Formula[N^{3 + epsilon}], then EXP !subseteq Formula[poly]. (5) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in BP[N^{2 + epsilon}], then EXP !subseteq BP[poly]. (6) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in (AC^0[6])[N^{1 + epsilon}], then EXP !subseteq AC^0[6]. These results are complemented by lower bounds for Gap-MCSP and Gap-MKtP against different models. For instance, the lower bound assumed in (1) holds for U_2-formulas of near-quadratic size, and lower bounds similar to (3)-(5) hold for various regimes of parameters. We also identify a natural computational model under which the hardness magnification threshold for Gap-MKtP lies below existing lower bounds: U_2-formulas that can compute parity functions at the leaves (instead of just literals). As a consequence, if one managed to adapt the existing lower bound techniques against such formulas to work with Gap-MKtP, then EXP !subseteq NC^1 would follow via hardness magnification.

We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC^0[oplus] circuits. Razborov [Alexander A. Razborov, 1987] and Smolensky [Roman Smolensky, 1987; Roman Smolensky, 1993] showed that Majority requires depth-d AC^0[oplus] circuits of size 2^{Omega(n^{1/2(d-1)})}. By using a divide-and-conquer approach, it is easy to show that Majority can be computed with depth-d AC^0[oplus] circuits of size 2^{O~(n^{1/(d-1)})}. This gap between upper and lower bounds has stood for nearly three decades. Somewhat surprisingly, we show that neither the upper bound nor the lower bound above is tight for large d. We show for d >= 5 that any symmetric function can be computed with depth-d AC^0[oplus] circuits of size exp(O~(n^{2/3 * 1/(d-4)})). Our upper bound extends to threshold functions (with a constant additive loss in the denominator of the double exponent). We improve the Razborov-Smolensky lower bound to show that for d >= 3 Majority requires depth-d AC^0[oplus] circuits of size 2^{Omega(n^{1/(2d-4)})}. For depths d <= 4, we are able to refine our techniques to get almost-optimal bounds: the depth-3 AC^0[oplus] circuit size of Majority is 2^{Theta~(n^{1/2})}, while its depth-4 AC^0[oplus] circuit size is 2^{Theta~(n^{1/4})}.

We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin’s notion [Leonid A. Levin, 1984] of Kolmogorov complexity. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability. This complexity measure gives rise to a decision problem over strings: MrKtP (The Minimum rKt Problem). We explore ideas from pseudorandomness to prove that MrKtP and its variants cannot be solved in randomized quasi-polynomial time. This exhibits a natural string compression problem that is provably intractable, even for randomized computations. Our techniques also imply that there is no n^{1 - epsilon}-approximate algorithm for MrKtP running in randomized quasi-polynomial time. Complementing this lower bound, we observe connections between rKt, the power of randomness in computing, and circuit complexity. In particular, we present the first hardness magnification theorem for a natural problem that is unconditionally hard against a strong model of computation.

We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or of the local predicate. Our two key conceptual contributions are: 1) We put forward the possibility that the choice of expander matters in expander-based cryptography. In particular, using expanders whose neighbour function has low circuit complexity might compromise the security of Goldreich's PRG and OWF in certain settings. 2) We show that the security of Goldreich's PRG and OWF is closely related to two other long-standing problems: Specifically, to the existence of unbalanced lossless expanders with low-complexity neighbor function, and to limitations on circuit lower bounds (i.e., natural proofs). In particular, our results further motivate the investigation of affine/local unbalanced lossless expanders and of average-case lower bounds against DNF-XOR circuits. We prove two types of technical results that support the above conceptual messages. First, we unconditionally break Goldreich's PRG when instantiated with a specific expander (whose existence we prove), for a class of predicates that match the parameters of the currently-best "hard" candidates, in the regime of quasi-polynomial stretch. Secondly, conditioned on the existence of expanders whose neighbor functions have extremely low circuit complexity, we present attacks on Goldreich's generator in the regime of polynomial stretch. As one corollary, conditioned on the existence of the foregoing expanders, we show that either the parameters of natural properties for several constant-depth circuit classes cannot be improved, even mildly; or Goldreich's generator is insecure in the regime of a large polynomial stretch, regardless of the predicate used.

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser [Eran Gat and Shafi Goldwasser, 2011]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed output with high probability. We explore pseudo-determinism in the settings of learning and approximation. Our goal is to simulate known randomized algorithms in these settings by pseudo-deterministic algorithms in a generic fashion - a goal we succinctly term pseudo-derandomization. Learning. In the setting of learning with membership queries, we first show that randomized learning algorithms can be derandomized (resp. pseudo-derandomized) under the standard hardness assumption that E (resp. BPE) requires large Boolean circuits. Thus, despite the fact that learning is an algorithmic task that requires interaction with an oracle, standard hardness assumptions suffice to (pseudo-)derandomize it. We also unconditionally pseudo-derandomize any {quasi-polynomial} time learning algorithm for polynomial size circuits on infinitely many input lengths in sub-exponential time. Next, we establish a generic connection between learning and derandomization in the reverse direction, by showing that deterministic (resp. pseudo-deterministic) learning algorithms for a concept class C imply hitting sets against C that are computable deterministically (resp. pseudo-deterministically). In particular, this suggests a new approach to constructing hitting set generators against AC^0[p] circuits by giving a deterministic learning algorithm for AC^0[p]. Approximation. Turning to approximation, we unconditionally pseudo-derandomize any poly-time randomized approximation scheme for integer-valued functions infinitely often in subexponential time over any samplable distribution on inputs. As a corollary, we get that the (0,1)-Permanent has a fully pseudo-deterministic approximation scheme running in sub-exponential time infinitely often over any samplable distribution on inputs. Finally, we {investigate} the notion of approximate canonization of Boolean circuits. We use a connection between pseudodeterministic learning and approximate canonization to show that if BPE does not have sub-exponential size circuits infinitely often, then there is a pseudo-deterministic approximate canonizer for AC^0[p] computable in quasi-polynomial time.

We show that for several natural problems of interest, complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification". Our examples of hardness magnification include: 1. Let MCSP be the decision problem whose YES instances are truth tables of functions with circuit complexity at most s(n). We show that if MCSP[2^√n] cannot be solved on average with zero error by formulas of linear (or even sub-linear) size, then NP does not have polynomial-size formulas. In contrast, Hirahara and Santhanam (2017) recently showed that MCSP[2^√n] cannot be solved in the worst case by formulas of nearly quadratic size. 2. If there is a c > 0 such that for each positive integer d there is an ε > 0 such that the problem of checking if an n-vertex graph in the adjacency matrix representation has a vertex cover of size (log n)^c cannot be solved by depth-d AC^0 circuits of size m^1+ε, where m = Θ(n^2), then NP does not have polynomial-size formulas. 3. Let (α, β)-MCSP[s] be the promise problem whose YES instances are truth tables of functions that are α-approximable by a circuit of size s(n), and whose NO instances are truth tables of functions that are not β-approximable by a circuit of size s(n). We show that for arbitrary 1/2c, let MKtP[c, s] be the promise problem whose YES instances are strings of Kt complexity at most c(N) and NO instances are strings of Kt complexity greater than s(N). We show that if there is a δ > 0 such that for each ε > 0, MKtP[N^ε, N^ε + 5 log(N)] requires Boolean circuits of size N^1+δ, then EXP is not contained in SIZE (poly). For each of the cases of magnification above, we observe that standard hardness assumptions imply much stronger lower bounds for these problems than we require for magnification. We further explore magnification as an avenue to proving strong lower bounds, and argue that magnification circumvents the "natural proofs" barrier of Razborov and Rudich (1997). Examining some standard proof techniques, we find that they fall just short of proving lower bounds via magnification. As one of our main open problems, we ask whether there are other meta-mathematical barriers to proving lower bounds that rule out approaches combining magnification with known techniques.

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have demonstrated the central role of this problem and its variations in diverse areas such as cryptography, derandomization, proof complexity, learning theory, and circuit lower bounds. The NP-hardness of computing the minimum numbers of terms in a DNF formula consistent with a given truth table was proved by W. Masek [William J. Masek, 1979] in 1979. In this work, we make the first progress in showing NP-hardness for more expressive classes of circuits, and establish an analogous result for the MCSP problem for depth-3 circuits of the form OR-AND-MOD_2. Our techniques extend to an NP-hardness result for MOD_m gates at the bottom layer under inputs from (Z / m Z)^n.

Let Addk,N denote the Boolean function which takes as input k strings of N bits each, representing k numbers a(1),…,a(k) in {0,1,…,2N-1}, and outputs 1 if and only if a(1) + … + a(k) ≥ 2N. Let MAJt,n denote a monotone unweighted threshold gate, i.e., the Boolean function which takes as input a single string x Ε {0,1}n and outputs 1 if and only if x1 + … + xn ≥ t. The function Addk,N may be viewed as a monotone function that performs addition, and MAJt,n may be viewed as a monotone gate that performs counting. We refer to circuits that are composed of MAJ gates as monotone majority circuits.

We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infinite sequence {pn} of primes and a randomized algorithm A running in expected sub-exponential time such that for each n, on input 1|pn|, A outputs pn with probability 1. In other words, our result provides a pseudodeterministic construction of primes in sub-exponential time which works infinitely often.

We show that any depth-d circuit for determining whether an n-node graph has an s-to-t path of length at most k must have size nΩ(k1/d/d) when k(n) ≤ n1/5, and nΩ(k1/5d/d) when k(n)≤ n. The previous best circuit size lower bounds were nkexp(−O(d)) (by Beame, Impagliazzo, and Pitassi (Computational Complexity 1998)) and nΩ((logk)/d) (following from a recent formula size lower bound of Rossman (STOC 2014)). Our lower bound is quite close to optimal, as a simple construction gives depth-d circuits of size nO(k2/d) for this problem (and strengthening our bound even to nkΩ(1/d) would require proving that undirected connectivity is not in NC1).

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and the class of all functions. We study this generalization of monotonicity from the vantage point of learning theory, establishing nearly matching upper and lower bounds on the uniform-distribution learnability of circuits in terms of the number of negations they contain. Our upper bounds are based on a new structural characterization of negation-limited circuits that extends a classical result of A.A. Markov. Our lower bounds, which employ Fourier-analytic tools from hardness amplification, give new results even for circuits with no negations (i.e. monotone functions).

We consider C-compression games, a hybrid model between computational and communication complexity. A C-compression game for a function f:{0,1}^n -> {0,1} is a two-party communication game, where the first party Alice knows the entire input x but is restricted to use strategies computed by C-circuits, while the second party Bob initially has no information about the input, but is computationally unbounded. The parties implement an interactive communication protocol to decide the value of f(x), and the communication cost of the protocol is the maximum number of bits sent by Alice as a function of n = |x|. We show that any AC_d[p]-compression protocol to compute Majority_n requires communication n / (log(n))^(2d + O(1)), where p is prime, and AC_d[p] denotes polynomial size unbounded fan-in depth-d Boolean circuits extended with modulo p gates. This bound is essentially optimal, and settles a question of Chattopadhyay and Santhanam (2012). This result has a number of consequences, and yields a tight lower bound on the total fan-in of oracle gates in constant-depth oracle circuits computing Majority_n. We define multiparty compression games, where Alice interacts in parallel with a polynomial number of players that are not allowed to communicate with each other, and communication cost is defined as the sum of the lengths of the longest messages sent by Alice during each round. In this setting, we prove that the randomized r-round AC^0[p]-compression cost of Majority_n is n^(Theta(1/r)). This result implies almost tight lower bounds on the maximum individual fan-in of oracle gates in certain restricted bounded-depth oracle circuits computing Majority_n. Stronger lower bounds for functions in NP would separate NP from NC^1. Finally, we consider the round separation question for two-party AC-compression games, and significantly improve known separations between r-round and (r+1)-round protocols, for any constant r.

Fort now and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class of boolean circuits C contained in P/poly of Boolean is exactly learnable with membership and equivalence queries in polynomial-time, then EXP^NP is not contained in C (the class EXP^NP was subsequently improved to EXP by Hitchcock and Harkins). In this paper, we improve on these results and show * If C is exactly learnable with membership and equivalence queries in polynomial-time, then DTIME(n^{\omega(1)}) is not contained in C. We obtain even stronger consequences if C is learnable in the mistake-bounded model, in which case we prove an average-case hardness result against C. * If C is learnable in polynomial time in the PAC model then PSPACE is not contained in C, unless PSPACE is contained in BPP. Removing this extra assumption from the statement of the theorem would provide an unconditional separation of PSPACE and BPP. * If C is efficiently learnable in the Correlational Statistical Query (CSQ) model, we show that there exists an explicit function f that is average-case hard for circuits in C. This result provides stronger average-case hardness guarantees than those obtained by SQ-dimension arguments (Blum et al. 1993). We also obtain a non-constructive extension of this result to the stronger Statistical Query (SQ) model. Similar results hold in the case where the learning algorithm runs in sub exponential time. Our proofs regarding exact and mistake-bounded learning are simple and self-contained, yield explicit hard functions, and show how to use mistake-bounded learners to "diagonalize"' over families of polynomial-size circuits. Our consequences for PAC learning lead to new proofs of Karp-Lipton-style collapse results, and the lower bounds from SQ learning make use of recent work relating combinatorial discrepancy to the existence of hard-on-average functions.