Symmetric Exponential Time Requires Near-Maximum Circuit Size

We show that there is a language in S 2 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 nearmaximum circuit lower bounds for the classes Σ 2 E, (Σ 2 E ∩ Π 2 E)/ 1 , and ZPE 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 E = E Σ2P (Miltersen, Vinodchandran, and Watanabe COCOON'99).

Our circuit lower bounds are corollaries of an unconditional zero-error pseudodeterministic algorithm with an NP oracle and one bit of advice (FZPP NP / 1 ) that solves the range avoidance problem infinitely often. This algorithm also implies unconditional infinitely-often pseudodeterministic FZPP NP / 1 constructions for Ramsey graphs, rigid matrices, two-source extractors, linear codes, and K poly -random strings with nearly optimal parameters.

Our proofs relativize. The two main technical ingredients are (1) Korten's P 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).