Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910529639940096 |
|---|---|
| author | Gamarnik, David Mossel, Elchanan Zadik, Ilias |
| author_facet | Gamarnik, David Mossel, Elchanan Zadik, Ilias |
| contents | We show that sharp thresholds for Boolean functions directly imply average-case circuit lower bounds. More formally we show that any Boolean function exhibiting a sharp enough threshold at \emph{arbitrary} critical density cannot be computed by Boolean circuits of bounded depth and polynomial size. We also prove a partial converse: if a monotone graph invariant Boolean function does not have a sharp threshold then it can be computed on average by a Boolean circuit of bounded depth and polynomial size.
Our general result also implies new average-case bounded depth circuit lower bounds in a variety of settings.
(a) ($k$-cliques) For $k=Θ(n)$, we prove that any circuit of depth $d$ deciding the presence of a size $k$ clique in a random graph requires exponential-in-$n^{Θ(1/d)}$ size.
(b)(random 2-SAT) We prove that any circuit of depth $d$ deciding the satisfiability of a random 2-SAT formula requires exponential-in-$n^{Θ(1/d)}$ size. To the best of our knowledge, this is the first bounded depth circuit lower bound for random $k$-SAT for any value of $k \geq 2.$ Our results also provide the first rigorous lower bound in agreement with a conjectured, but debated, "computational hardness" of random $k$-SAT around its satisfiability threshold.
(c)(Statistical estimation -- planted $k$-clique) Over the recent years, multiple statistical estimation problems have also been proven to exhibit a "statistical" sharp threshold, called the All-or-Nothing (AoN) phenomenon. We show that AoN also implies circuit lower bounds for statistical problems. As a simple corollary of that, we prove that any circuit of depth $d$ that solves to information-theoretic optimality a "dense" variant of the celebrated planted $k$-clique problem requires exponential-in-$n^{Θ(1/d)}$ size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_04204 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique Gamarnik, David Mossel, Elchanan Zadik, Ilias Computational Complexity Probability Statistics Theory We show that sharp thresholds for Boolean functions directly imply average-case circuit lower bounds. More formally we show that any Boolean function exhibiting a sharp enough threshold at \emph{arbitrary} critical density cannot be computed by Boolean circuits of bounded depth and polynomial size. We also prove a partial converse: if a monotone graph invariant Boolean function does not have a sharp threshold then it can be computed on average by a Boolean circuit of bounded depth and polynomial size. Our general result also implies new average-case bounded depth circuit lower bounds in a variety of settings. (a) ($k$-cliques) For $k=Θ(n)$, we prove that any circuit of depth $d$ deciding the presence of a size $k$ clique in a random graph requires exponential-in-$n^{Θ(1/d)}$ size. (b)(random 2-SAT) We prove that any circuit of depth $d$ deciding the satisfiability of a random 2-SAT formula requires exponential-in-$n^{Θ(1/d)}$ size. To the best of our knowledge, this is the first bounded depth circuit lower bound for random $k$-SAT for any value of $k \geq 2.$ Our results also provide the first rigorous lower bound in agreement with a conjectured, but debated, "computational hardness" of random $k$-SAT around its satisfiability threshold. (c)(Statistical estimation -- planted $k$-clique) Over the recent years, multiple statistical estimation problems have also been proven to exhibit a "statistical" sharp threshold, called the All-or-Nothing (AoN) phenomenon. We show that AoN also implies circuit lower bounds for statistical problems. As a simple corollary of that, we prove that any circuit of depth $d$ that solves to information-theoretic optimality a "dense" variant of the celebrated planted $k$-clique problem requires exponential-in-$n^{Θ(1/d)}$ size. |
| title | Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique |
| topic | Computational Complexity Probability Statistics Theory |
| url | https://arxiv.org/abs/2311.04204 |