__
Revision #1 to TR23-156 | 4th April 2024 15:38
__
#### Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform

**Abstract:**
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.

**Changes to previous version:**
Updated results; Fixed a few errors.

__
TR23-156 | 26th October 2023 22:30
__

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

TR23-156
Authors:

Zeyong Li
Publication: 28th October 2023 09:54

Downloads: 825

Keywords:

**Abstract:**
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.