Local Enumeration and Majority Lower Bounds
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916256929546240 |
|---|---|
| author | Gurumukhani, Mohit Paturi, Ramamohan Pudlák, Pavel Saks, Michael Talebanfard, Navid |
| author_facet | Gurumukhani, Mohit Paturi, Ramamohan Pudlák, Pavel Saks, Michael Talebanfard, Navid |
| contents | Depth-3 circuit lower bounds and $k$-SAT algorithms are intimately related; the state-of-the-art $Σ^k_3$-circuit lower bound and the $k$-SAT algorithm are based on the same combinatorial theorem. In this paper we define a problem which reveals new interactions between the two. Define Enum($k$, $t$) problem as: given an $n$-variable $k$-CNF and an initial assignment $α$, output all satisfying assignments at Hamming distance $t$ from $α$, assuming that there are no satisfying assignments of Hamming distance less than $t$ from $α$. Observe that: an upper bound $b(n, k, t)$ on the complexity of Enum($k$, $t$) implies:
- Depth-3 circuits: Any $Σ^k_3$ circuit computing the Majority function has size at least $\binom{n}{\frac{n}{2}}/b(n, k, \frac{n}{2})$.
- $k$-SAT: There exists an algorithm solving $k$-SAT in time $O(\sum_{t = 1}^{n/2}b(n, k, t))$.
A simple construction shows that $b(n, k, \frac{n}{2}) \ge 2^{(1 - O(\log(k)/k))n}$. Thus, matching upper bounds would imply a $Σ^k_3$-circuit lower bound of $2^{Ω(\log(k)n/k)}$ and a $k$-SAT upper bound of $2^{(1 - Ω(\log(k)/k))n}$. The former yields an unrestricted depth-3 lower bound of $2^{ω(\sqrt{n})}$ solving a long standing open problem, and the latter breaks the Super Strong Exponential Time Hypothesis.
In this paper, we propose a randomized algorithm for Enum($k$, $t$) and introduce new ideas to analyze it. We demonstrate the power of our ideas by considering the first non-trivial instance of the problem, i.e., Enum($3$, $\frac{n}{2}$). We show that the expected running time of our algorithm is $1.598^n$, substantially improving on the trivial bound of $3^{n/2} \simeq 1.732^n$. This already improves $Σ^3_3$ lower bounds for Majority function to $1.251^n$. The previous bound was $1.154^n$ which follows from the work of Håstad, Jukna, and Pudlák (Comput. Complex.'95). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_09134 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Local Enumeration and Majority Lower Bounds Gurumukhani, Mohit Paturi, Ramamohan Pudlák, Pavel Saks, Michael Talebanfard, Navid Computational Complexity Depth-3 circuit lower bounds and $k$-SAT algorithms are intimately related; the state-of-the-art $Σ^k_3$-circuit lower bound and the $k$-SAT algorithm are based on the same combinatorial theorem. In this paper we define a problem which reveals new interactions between the two. Define Enum($k$, $t$) problem as: given an $n$-variable $k$-CNF and an initial assignment $α$, output all satisfying assignments at Hamming distance $t$ from $α$, assuming that there are no satisfying assignments of Hamming distance less than $t$ from $α$. Observe that: an upper bound $b(n, k, t)$ on the complexity of Enum($k$, $t$) implies: - Depth-3 circuits: Any $Σ^k_3$ circuit computing the Majority function has size at least $\binom{n}{\frac{n}{2}}/b(n, k, \frac{n}{2})$. - $k$-SAT: There exists an algorithm solving $k$-SAT in time $O(\sum_{t = 1}^{n/2}b(n, k, t))$. A simple construction shows that $b(n, k, \frac{n}{2}) \ge 2^{(1 - O(\log(k)/k))n}$. Thus, matching upper bounds would imply a $Σ^k_3$-circuit lower bound of $2^{Ω(\log(k)n/k)}$ and a $k$-SAT upper bound of $2^{(1 - Ω(\log(k)/k))n}$. The former yields an unrestricted depth-3 lower bound of $2^{ω(\sqrt{n})}$ solving a long standing open problem, and the latter breaks the Super Strong Exponential Time Hypothesis. In this paper, we propose a randomized algorithm for Enum($k$, $t$) and introduce new ideas to analyze it. We demonstrate the power of our ideas by considering the first non-trivial instance of the problem, i.e., Enum($3$, $\frac{n}{2}$). We show that the expected running time of our algorithm is $1.598^n$, substantially improving on the trivial bound of $3^{n/2} \simeq 1.732^n$. This already improves $Σ^3_3$ lower bounds for Majority function to $1.251^n$. The previous bound was $1.154^n$ which follows from the work of Håstad, Jukna, and Pudlák (Comput. Complex.'95). |
| title | Local Enumeration and Majority Lower Bounds |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2403.09134 |