Theorem 1.3: depth- circuits for -OV in dimension need gates
OpenHypercliqueAC0.FixedDepth.Supplement.theorem_1_3complexity-theoryorthogonal-vectorsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
An instance of consists of lists of vectors in , and
A depth- circuit is a De Morgan circuit of depth at most , is its number of noninput gates, and is the base-two logarithm. The theorem has two claims.
- For every integer and every there is an exponent , depending only on and , such that for every fixed there is with the following property: for every and every dimension , every depth- circuit computing satisfies
- For every integer , every and every there are an exponent and such that for every and every , every depth- circuit computing satisfies
The exhaustive-search circuit uses about gates, so the bound shows that exhaustive search is nearly optimal for -OV at every fixed depth in polylogarithmic dimension.
Formalization Note is the published ErrAmpOV.kOV k n d, whose variable (i, j, q) is coordinate of vector of list . In the first claim the exponent is chosen before , so it is uniform in ; in the second it may depend on . Every dimension above the threshold is covered.
Differences from the source:
- encoding: lists of vectors in → Boolean variables indexed by (the published
ErrAmpOV.kOV); reason: a relabeling bijection preserves every instance - encoding: integers and the threshold for "sufficiently large " → natural numbers, with real casts before exponentiation; reason: all are counts or lower thresholds, and a natural threshold can dominate any integer threshold
- encoding: the §3.2 convention that every gate reaches the output → arbitrary circuits, including unused gates and repeated input sources, with gate count equal to the gate-list length; reason: pruning unused gates and deleting repeated sources preserve output and depth and cannot increase gate count
- reading: "" in the first claim → there is a real exponent chosen after and before , and the claim holds for every ; reason: the subscript names exactly , and the proof takes depending only on
- reading: "" in the second claim → there is a real exponent chosen after ; reason: the subscript names exactly
Preamble
import Mathlib import Definitions.Def_MantriCVQ_ACCircuit import Definitions.Def_ErrAmpOV_kOV noncomputable section
Formal statement
namespace HypercliqueAC0.FixedDepth.Supplement
/-- Theorem 1.3, p. 4 (PDF 6), both claims. `k-OV_{n,d}` is `ErrAmpOV.kOV k n d` on the
variables `Fin k × Fin n × Fin d`; `log` is base two. First claim: the exponent `K` of the
dimension threshold `(log n)^K` depends only on `h, ε` (it is chosen before `k`), and the
threshold `n₀` on `h, ε, k`. Second claim: the exponent `K'` may depend on `h, k, ε`. Every
dimension `d` above the threshold is covered. -/
theorem theorem_1_3 :
(∀ h : ℕ, 1 ≤ h → ∀ ε : ℝ, 0 < ε → ∃ K : ℝ, ∀ k : ℕ, 2 ≤ k →
∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n → ∀ d : ℕ, (Real.logb 2 n) ^ K ≤ (d : ℝ) →
∀ C : MantriCVQ.ACCircuit (Fin k × Fin n × Fin d), C.depth ≤ h →
(∀ x, C.eval x = ErrAmpOV.kOV k n d x) →
(n : ℝ) ^ ((k : ℝ) * (1 - ε)) ≤ (C.gates.length : ℝ)) ∧
(∀ h : ℕ, 1 ≤ h → ∀ ε : ℝ, 0 < ε → ∀ k : ℕ, 2 ≤ k → ∃ K : ℝ,
∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n → ∀ d : ℕ, (Real.logb 2 n) ^ K ≤ (d : ℝ) →
∀ C : MantriCVQ.ACCircuit (Fin k × Fin n × Fin d), C.depth ≤ h →
(∀ x, C.eval x = ErrAmpOV.kOV k n d x) →
(n : ℝ) ^ ((k : ℝ) - ε) ≤ (C.gates.length : ℝ)) := by sorry
end HypercliqueAC0.FixedDepth.Supplement
Source
Nikolai Chukhin, Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors, STOC 2027 submission #830 (October 2026), source.pdf SHA-256 bd73fd887fe562527226e0ea2da24a55552a73cf89c2e90406a28965424a12de, p.4 (PDF p.6), Theorem 1.3; k-OV defined in §3.1 p.10 (PDF p.12); proof §7 pp.22-23 (PDF pp.24-25)