Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR23-156 | 26th October 2023 22:30

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

RSS-Feed




TR23-156
Authors: Zeyong Li
Publication: 28th October 2023 09:54
Downloads: 464
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