Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform

Abstract

In a recent breakthrough, Chen, Hirahara and Ren prove that ${\mathsf{S}}_2\mathsf{E}{/}_1\not\subset \mathsf{SIZE}[2^n/n]$ by giving a single-valued $\mathsf{F}{\mathsf{S}}_2\mathsf{P}$ algorithm for the Range Avoidance Problem ($\mathsf{Avoid}$) that works for infinitely many input size $n$. Building on their work, we present a simple single-valued $\mathsf{F}{\mathsf{S}}_2\mathsf{P}$ algorithm for $\mathsf{Avoid}$ that works for all input size $n$. As a result, we obtain the circuit lower bound ${\mathsf{S}}_2\mathsf{E}\not\subset i.o.$-$\mathsf{SIZE}[2^n/n]$ and many other corollaries: 1. Almost-everywhere near-maximum circuit lower bound for ${\mathsf{\Sigma }}_2\mathsf{E}\cap {\mathsf{\Pi }}_2\mathsf{E}$ and ${\mathsf{ZPE}}^{\mathsf{NP}}$. 2. Pseudodeterministic ${\mathsf{FZPP}}^{\mathsf{NP}}$ constructions for: Ramsey graphs, rigid matrices, pseudorandom generators, two-source extractors, linear codes, hard truth tables, and $K^{poly}$-random strings.