Lune

FOCS2024Top-tier venue

Reverse Mathematics of Complexity Lower Bounds

Lijie Chen, Jiatu Li, Igor C. Oliveira

Abstract

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.

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.

7 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
  • Symmetric Exponential Time Requires Near-Maximum Circuit Size cites The Hardest Explicit Construction
  • Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap cites The Hardest Explicit Construction
  • Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap cites Symmetric Exponential Time Requires Near-Maximum Circuit Size
  • 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 Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
  • Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds cites The Hardest Explicit Construction
  • 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
  • Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic cites The Hardest Explicit Construction
  • Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic cites Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
  • Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets cites The Hardest Explicit Construction
  • Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets cites Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
  • Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform cites The Hardest Explicit Construction
  • Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform cites Symmetric Exponential Time Requires Near-Maximum Circuit Size
  • Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform cites Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers7

  1. Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the GapStefan Grosser, Marco CarmosinoSTOC 2025 · 3 citations
  2. Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower BoundsJiawei Li, Yuhao Li, Hanlin RenSTOC 2026 · 3 citations
  3. The Weak Rank Principle: Lower Bounds and ApplicationsMichal Garlík, Svyatoslav Gryaznov, Hanlin Ren, Iddo TzameretSTOC 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. Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting SetsAlbert Atserias, Iddo TzameretSTOC 2025 · 1 citation

Builds on6

  1. The Hardest Explicit ConstructionOliver KortenFOCS 2021 · 18 citations
  2. Indistinguishability Obfuscation, Range Avoidance, and Bounded ArithmeticRahul Ilango, Jiatu Li, R. Ryan WilliamsSTOC 2023 · 17 citations
  3. Strong co-nondeterministic lower bounds for NP cannot be proved feasiblyJán Pich, Rahul SanthanamSTOC 2021 · 10 citations
  4. Symmetric Exponential Time Requires Near-Maximum Circuit SizeLijie Chen, Shuichi Hirahara, Hanlin RenSTOC 2024 · 9 citations
  5. Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly UniformZeyong LiSTOC 2024 · 9 citations

Related papers

  1. A Theory for Probabilistic Polynomial-Time ReasoningLijie Chen, Jiatu Li, Igor C. Oliveira, Ryan WilliamsSTOC 2026 · 1 citation
  2. Unprovability of Strong Complexity Lower Bounds in Bounded ArithmeticJiatu Li, Igor C. OliveiraSTOC 2023 · 2 citations
  3. LEARN-Uniform Circuit Lower Bounds and Provability in Bounded ArithmeticMarco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. OliveiraFOCS 2021 · 6 citations
  4. Meta-Mathematics of Algebraic ComplexityMichal Garlík, Svyatoslav Gryaznov, Jiaqi Lu, Rahul Santhanam et al.LICS 2026
  5. Oracles Just for Fan: A Robust Computational Interpretation of the Fan TheoremTitouan Leclercq, Étienne MiqueyLICS 2026
Dusk over the sea between two cliffs drawn in fine vertical lines