Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2310.17762 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909160640086016 |
|---|---|
| author | Li, Zeyong |
| author_facet | Li, Zeyong |
| contents | 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 {i.o.}$-$\mathsf{SIZE}[2^n/n]$ and many other corollaries:
1. Almost-everywhere near-maximum circuit lower bound for $\mathsf{Σ_2E} \cap \mathsf{Π_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_17762 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform Li, Zeyong Computational Complexity 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 {i.o.}$-$\mathsf{SIZE}[2^n/n]$ and many other corollaries: 1. Almost-everywhere near-maximum circuit lower bound for $\mathsf{Σ_2E} \cap \mathsf{Π_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. |
| title | Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2310.17762 |