Lune

FOCS2021Top-tier venue

LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira

Abstract

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 allc≥1c\geq 1, there isL∈PL\in \mathsf{P}that is not computable by circuits of sizen⋅(log⁡n)cn\cdot(\log n)^{c}generated in deterministic polynomial time witho(log⁡n/log⁡log⁡n)o(\log n/\log\log n)equivalence queries toLL. In other words, small circuits forLLcannot be efficiently learned using a bounded number of EQs. –For eachk≥1k\geq 1, there isL∈NPL\in \mathsf{NP}such that circuits forLLof sizeO(nk)O(n^{k})cannot be learned in deterministic polynomial time with access tono(1)n^{o(1)}EQs. –For eachk≥1k\geq 1, there is a problem in promise-ZPP that is not in FZPP-uniformSIZE[nk]\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 inSIZE[n3]?)\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 “NP⊈BPP∧NP⊂io−P/poly\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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

8 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?) cites Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
  • Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?) cites Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
  • Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap cites Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
  • Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap cites Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization
  • Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds cites Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
  • Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds cites Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
  • Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds cites Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
  • Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic cites Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
  • Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic cites Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers8

  1. Indistinguishability Obfuscation, Range Avoidance, and Bounded ArithmeticRahul Ilango, Jiatu Li, R. Ryan WilliamsSTOC 2023 · 17 citations
  2. Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the GapStefan Grosser, Marco CarmosinoSTOC 2025 · 3 citations
  3. Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower BoundsJiawei Li, Yuhao Li, Hanlin RenSTOC 2026 · 3 citations
  4. Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)Lijie Chen, Ron D. Rothblum, Roei TellSTOC 2025 · 2 citations
  5. Unprovability of Strong Complexity Lower Bounds in Bounded ArithmeticJiatu Li, Igor C. OliveiraSTOC 2023 · 2 citations

Builds on3

  1. Almost-Everywhere Circuit Lower Bounds from Non-Trivial DerandomizationLijie Chen, Xin Lyu, R. Ryan WilliamsFOCS 2020 · 29 citations
  2. Strong co-nondeterministic lower bounds for NP cannot be proved feasiblyJán Pich, Rahul SanthanamSTOC 2021 · 10 citations
  3. Pseudodeterministic algorithms and the structure of probabilistic timeZhenjian Lu, Igor C. Oliveira, Rahul SanthanamSTOC 2021 · 1 citation

Related papers

  1. A Theory for Probabilistic Polynomial-Time ReasoningLijie Chen, Jiatu Li, Igor C. Oliveira, Ryan WilliamsSTOC 2026 · 1 citation
  2. Reverse Mathematics of Complexity Lower BoundsLijie Chen, Jiatu Li, Igor C. OliveiraFOCS 2024 · 4 citations
  3. On the Consistency of Circuit Lower Bounds for Non-deterministic TimeAlbert Atserias, Sam Buss, Moritz MüllerSTOC 2023 · 1 citation
  4. Unstructured Hardness to Average-Case RandomnessLijie Chen, Ron D. Rothblum, Roei TellFOCS 2022 · 8 citations
  5. NP-Hardness of Learning Programs and Partial MCSPShuichi HiraharaFOCS 2022 · 24 citations
Dusk over the sea between two cliffs drawn in fine vertical lines