Symmetric Exponential Time Requires Near-Maximum Circuit Size
Preprint
Abstract
We show that there is a language in $\mathsf{S}_2\mathsf{E}/_1$ (symmetric exponential time with one bit of advice) with circuit complexity at least $2^n/n$. In particular, the above also implies the same near-maximum circuit lower bounds for the classes $Σ_2\mathsf{E}$, $(Σ_2\mathsf{E}\capΠ_2\mathsf{E})/_1$, and $\mathsf{ZPE}^{\mathsf{NP}}/_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 $Δ_3\mathsf{E} = \mathsf{E}^{Σ_2\mathsf{P}}$ (Miltersen, Vinodchandran, and Watanabe COCOON'99). Our circuit lower bounds are corollaries of an unconditional zero-error pseudodeterministic algorithm with an $\mathsf{NP}$ oracle and one bit of advice ($\mathsf{FZPP}^{\mathsf{NP}}/_1$) that solves the range avoidance problem infinitely often. This algorithm also implies unconditional infinitely-often pseudodeterministic $\mathsf{FZPP}^{\mathsf{NP}}/_1$ constructions for Ramsey graphs, rigid matrices, two-source extractors, linear codes, and $\mathrm{K}^{\mathrm{poly}}$-random strings with nearly optimal parameters. Our proofs relativize. The two main technical ingredients are (1) Korten's $\mathsf{P}^{\mathsf{NP}}$ reduction from the range avoidance problem to constructing hard truth tables (FOCS'21), which was in turn inspired by a result of Jeřábek on provability in Bounded Arithmetic (Ann. Pure Appl. Log. 2004); and (2) the recent iterative win-win paradigm of Chen, Lu, Oliveira, Ren, and Santhanam (FOCS'23).
Keywords
All Related Versions
This publication has 46 references indexed in Scilit:
- The Power of Natural Properties as Oraclescomputational complexity, 2023
- Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential HierarchyLecture Notes in Computer Science, 1999
- Symmetric alternation captures BPPcomputational complexity, 1998
- Oracles and Queries That Are Sufficient for Exact LearningJournal of Computer and System Sciences, 1996
- Efficient Checking of Polynomials and Proofs and the Hardness of Appoximation ProblemsLecture Notes in Computer Science, 1995
- BPP has subexponential time simulations unlessEXPTIME has publishable proofscomputational complexity, 1993
- On using oracles that compute valuesLecture Notes in Computer Science, 1993
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- Graph-theoretic arguments in low-level complexity1977
- The Synthesis of Two-Terminal Switching CircuitsBell System Technical Journal, 1949