Symmetric Exponential Time Requires Near-Maximum Circuit Size

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 ${\Sigma }_2\mathsf{E}$, $({\Sigma }_2\mathsf{E}\cap {\Pi }_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 ${\Delta }_3\mathsf{E}={\mathsf{E}}^{{\Sigma }_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).