Metraipolis › archive › dc_4e2ccd93d1d6

Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors — arXiv:2611.06231

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.06231
License (as archived)
CC0-1.0
Archived
2026-11-05T18:32:02.731Z
SHA-256 of the archived text
8c729b459b9d675fbcc178a054d18044a21cf926f53a2e9b1ad11154e876ad5a
Stable URL of this page
https://metraipolis.com/documento/dc_4e2ccd93d1d6

How to cite

Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors — arXiv:2611.06231 — arXiv (en), https://arxiv.org/abs/2611.06231 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4e2ccd93d1d6 (Metraipolis archive dc_4e2ccd93d1d6, sha256 8c729b459b9d675fbcc178a054d18044a21cf926f53a2e9b1ad11154e876ad5a)
BibTeX
@misc{dc4e2ccd93d1d6,
  title = {Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors — arXiv:2611.06231},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06231},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4e2ccd93d1d6; sha256 8c729b459b9d675fbcc178a054d18044a21cf926f53a2e9b1ad11154e876ad5a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06231. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A hyperclique in an $r$-uniform hypergraph is a set of vertices in which every $r$-subset is an edge. A simple exhaustive search algorithm detects a hyperclique on $\ell$ vertices in an $r$-uniform hypergraph on $m$ vertices by checking all $\binom{m}{\ell}$ sets of $\ell$ vertices. This algorithm can be expressed as a depth-two circuit with at most $m^\ell$ gates and wires. For hypercliques of *constant* size, Amano (2010) showed that this circuit is almost optimal: for large $r$, constant-depth circuits need $m^{\ell(1-O(\log r/r))}$ wires. We prove that this circuit remains hard to beat even for hypercliques of *polynomial* size. More precisely, circuits of depth $h$ need $m^{\Omega(\ell)}$ gates for $\ell\leq m^{1/h-\varepsilon}$, and $m^{\ell(1-O(\log r/r))}$ gates for $\ell=m^{o(1)}$ that tends to infinity. Our hyperclique bound and the method behind it also lead to lower bounds for two central problems of fine-grained complexity. First, we extend the bound $n^{k/4}$ of Rossman (2008) for $k$-Clique from cliques of *constant* size to cliques of *polynomial* size: circuits of depth $h$ detecting a clique on $k$ vertices in an $n$-vertex graph need $n^{\Omega(k)}$ gates for $k\leq n^{1/(h-1)-\varepsilon}$. Second, a reduction of Choudhury, Limaye, Sreenivasaiah, and Srinivasan (2026) turns our hyperclique bound into a lower bound of $n^{k-\varepsilon}$ gates for $k$-Orthogonal Vectors ($k$-OV) at every fixed depth for vectors of dimension $\log^{O(1)} n$; this proves the $k$-OV Conjecture for constant-depth circuits in polylogarithmic dimension. Finally, for $2$-OV in logarithmic dimension, we give a simple proof that depth-three circuits need $\Omega(n^2)$ wires, which answers a question of Kane and Williams (2019).

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.06231 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:34.064Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).