Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-156 | 4th April 2024 15:38

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

RSS-Feed




Revision #1
Authors: Zeyong Li
Accepted on: 4th April 2024 15:38
Downloads: 189
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$ 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.


Paper:

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: 955
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.



ISSN 1433-8092 | Imprint