Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2402.05451 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914671151284224 |
|---|---|
| author | Mardia, Jay Verchand, Kabir Aladin Wein, Alexander S. |
| author_facet | Mardia, Jay Verchand, Kabir Aladin Wein, Alexander S. |
| contents | We consider the problem of detecting a planted clique of size $k$ in a random graph on $n$ vertices. When the size of the clique exceeds $Θ(\sqrt{n})$, polynomial-time algorithms for detection proliferate. We study faster -- namely, sublinear time -- algorithms in the high-signal regime when $k = Θ(n^{1/2 + δ})$, for some $δ> 0$. To this end, we consider algorithms that non-adaptively query a subset $M$ of entries of the adjacency matrix and then compute a low-degree polynomial function of the revealed entries. We prove a computational phase transition for this class of non-adaptive low-degree algorithms: under the scaling $\lvert M \rvert = Θ(n^γ)$, the clique can be detected when $γ> 3(1/2 - δ)$ but not when $γ< 3(1/2 - δ)$. As a result, the best known runtime for detecting a planted clique, $\widetilde{O}(n^{3(1/2-δ)})$, cannot be improved without looking beyond the non-adaptive low-degree class.
Our proof of the lower bound -- based on bounding the conditional low-degree likelihood ratio -- reveals further structure in non-adaptive detection of a planted clique. Using (a bound on) the conditional low-degree likelihood ratio as a potential function, we show that for every non-adaptive query pattern, there is a highly structured query pattern of the same size that is at least as effective. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05451 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Low-degree phase transitions for detecting a planted clique in sublinear time Mardia, Jay Verchand, Kabir Aladin Wein, Alexander S. Data Structures and Algorithms Computational Complexity Machine Learning We consider the problem of detecting a planted clique of size $k$ in a random graph on $n$ vertices. When the size of the clique exceeds $Θ(\sqrt{n})$, polynomial-time algorithms for detection proliferate. We study faster -- namely, sublinear time -- algorithms in the high-signal regime when $k = Θ(n^{1/2 + δ})$, for some $δ> 0$. To this end, we consider algorithms that non-adaptively query a subset $M$ of entries of the adjacency matrix and then compute a low-degree polynomial function of the revealed entries. We prove a computational phase transition for this class of non-adaptive low-degree algorithms: under the scaling $\lvert M \rvert = Θ(n^γ)$, the clique can be detected when $γ> 3(1/2 - δ)$ but not when $γ< 3(1/2 - δ)$. As a result, the best known runtime for detecting a planted clique, $\widetilde{O}(n^{3(1/2-δ)})$, cannot be improved without looking beyond the non-adaptive low-degree class. Our proof of the lower bound -- based on bounding the conditional low-degree likelihood ratio -- reveals further structure in non-adaptive detection of a planted clique. Using (a bound on) the conditional low-degree likelihood ratio as a potential function, we show that for every non-adaptive query pattern, there is a highly structured query pattern of the same size that is at least as effective. |
| title | Low-degree phase transitions for detecting a planted clique in sublinear time |
| topic | Data Structures and Algorithms Computational Complexity Machine Learning |
| url | https://arxiv.org/abs/2402.05451 |