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

Zeyong Li

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 A…