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

In a recent breakthrough, Chen, Hirahara and Ren [CHR24] prove that S2E/1 ⊂ SIZE[2 n /n] by giving a single-valued FS2P algorithm for the Range Avoidance Problem (Avoid) that works for infinitely many input size n.

Building on their work, we present a simple single-valued FS2P algorithm for Avoid that works for all input size n. As a result, we obtain the circuit lower bound S2E ⊂ i.o.-SIZE[2 n /n] and many other corollaries:

1. Almost-everywhere near-maximum circuit lower bound for Σ2E ∩ Π2E and ZPE NP .

2. Pseudodeterministic FZPP NP constructions for combinatorial objects such as: Ramsey graphs, rigid matrices, pseudorandom generators, two-source extractors, linear codes, hard truth tables, and K poly -random strings.