Publication
Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors
Preprint, 2026. PDF
Abstract
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 \le 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 \le 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).