In a recent breakthrough, Chen, Hirahara and Ren prove that S$_2$E/$_1 \not\subset$ SIZE$[2^n/n]$ by giving a single-valued FS$_2$P 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 FS$_2$P algorithm for Avoid that works for all input size $n$. As a result, we obtain the circuit lower bound S$_2$E $\not\subset$ i.o.-SIZE$[2^n/n]$ and many other corollaries:
1.Almost-everywhere near-maximum circuit lower bound for $\Sigma_2$E $\cap \Pi_2$E and ZPE$^{NP}$.
2.Pseudodeterministic FZPP$^{NP}$ constructions for: Ramsey graphs, rigid matrices, pseudorandom generators, two-source extractors, linear codes, hard truth tables, and K$^{poly}$-random strings.
Updated results; Fixed a few errors.
In a recent breakthrough, Chen, Hirahara and Ren prove that S$_2$E/$_1 \not\subset$ SIZE$[2^n/n]$ by giving a single-valued FS$_2$P 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 FS$_2$P algorithm for Avoid that works for all input size $n$. As a result, we obtain the circuit lower bound S$_2$E $\not\subset$ SIZE$[2^n/n]$ and many other corollaries:
1.Near-maximum circuit lower bound for $\Sigma_2$E $\cap \Pi_2$E and ZPE$^{NP}$.
2.Pseudodeterministic FZPP$^{NP}$ constructions for: Ramsey graphs, rigid matrices, pseudorandom generators, two-source extractors, linear codes, hard truth tables, and K$^{poly}$-random strings.