Symmetric Exponential Time Requires Near-Maximum Circuit Size

Lijie Chen, Shuichi Hirahara, Hanlin Ren

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