4
[2310.17762] Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simp...
source link: https://arxiv.org/abs/2310.17762
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Computational Complexity
[Submitted on 26 Oct 2023]
Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
In a recent breakthrough, Chen, Hirahara and Ren prove that \mathsf{S_2E}/_1 \not\subset \mathsf{SIZE}[2^n/n] by giving a single-valued \mathsf{FS_2P} algorithm for the Range Avoidance Problem (\mathsf{Avoid}) that works for infinitely many input size n.
Building on their work, we present a simple single-valued \mathsf{FS_2P} algorithm for \mathsf{Avoid} that works for all input size n. As a result, we obtain the circuit lower bound \mathsf{S_2E} \not\subset \mathsf{SIZE}[2^n/n] and many other corollaries:
1. Near-maximum circuit lower bound for \mathsf{\Sigma_2E} \cap \mathsf{\Pi_2E} and \mathsf{ZPE}^{\mathsf{NP}}.
2. Pseudodeterministic \mathsf{FZPP}^{\mathsf{NP}} constructions for: Ramsey graphs, rigid matrices, pseudorandom generators, two-source extractors, linear codes, hard truth tables, and K^{poly}-random strings.
| Subjects: | Computational Complexity (cs.CC) |
| Cite as: | arXiv:2310.17762 [cs.CC] |
| (or arXiv:2310.17762v1 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2310.17762 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK