Symmetric Exponential Time Requires Near-Maximum Circuit Size

We show that there is a language in \(\textsf{S}_2\textsf {E}\) (symmetric exponential time) that requires circuit complexity at least \(2^n/n\) on every input length. In particular, the above also implies the same near-maximum circuit lower bounds for \(\Sigma _2\textsf {E}\cap \Pi _2\textsf {E}\) and \(\mathsf {ZPE}^{\textsf {NP}}\) . Our proofs relativise. Previously, only “half-exponential” circuit lower bounds for the aforementioned complexity classes were known, and the smallest complexity class known to require exponential circuit complexity was \(\Delta _3\textsf {E}= \textsf {E}^{\Sigma _2\textsf{P}}\) (Miltersen, Vinodchandran, and Watanabe COCOON’99). Our circuit lower bounds are corollaries of an unconditional zero-error pseudodeterministic algorithm with an \(\textsf {NP}\) oracle that solves the Range Avoidance problem. This algorithm also implies unconditional pseudodeterministic \(\textsf {FZPP}^{\textsf {NP}}\) constructions for Ramsey graphs, rigid matrices, two-source extractors, linear codes, and \(\mathrm{K}^{\mathrm{poly}}\) -random strings with nearly optimal parameters.