Math Conjectures

Orthogonal Vectors Conjecture

OPENMajorConjectureProposed c. 2005 · Standard version

Canonical statement

For every ε>0\varepsilon>0, there is a constant c>0c>0 such that no randomized bounded-error O(n2−ε)O(n^{2-\varepsilon})-time algorithm, given A,B⊆{0,1}dA,B\subseteq\{0,1\}^{d} with ∣A∣=∣B∣=n|A|=|B|=n and d=clog⁡nd=c\log n, decides whether there exist a∈A,b∈Ba\in A,b\in B with
⟨a,b⟩=0. \langle a,b\rangle=0.
View source LaTeX
For every \(\varepsilon>0\), there is a constant \(c>0\)
such that no randomized bounded-error
\(O(n^{2-\varepsilon})\)-time algorithm, given
\(A,B\subseteq\{0,1\}^{d}\) with
\(|A|=|B|=n\) and \(d=c\log n\), decides whether there exist
\(a\in A,b\in B\) with
\[
  \langle a,b\rangle=0.
\]
TCS-021:[Williams2005OV][AbboudWilliamsWang2015OV][Bringmann2019FineGrained]
Theoretical computer scienceOperations research

Notes

The Orthogonal Vectors conjecture concerns the following problem: given families A,B⊆{0,1}dA,B\subseteq\{0,1\}^d with ∣A∣=∣B∣=n|A|=|B|=n and dimension d=clog⁡nd=c\log n, decide whether some a∈Aa\in A and b∈Bb\in B satisfy ⟨a,b⟩=0\langle a,b\rangle=0. The conjecture asserts that for every ε>0\varepsilon>0 there is a constant cc for which no randomized bounded-error algorithm runs in time O(n2−ε)O(n^{2-\varepsilon}). Its modern formulation emerged around 2005 from Williams's reduction of CNF satisfiability to this problem, which shows that SETH implies the conjecture [Williams2005OV].

Algorithmic progress via the polynomial method gives savings over the quadratic bound that fall short of a truly subquadratic O(n2−ε)O(n^{2-\varepsilon}) running time in the d=clog⁡nd=c\log n regime [AbboudWilliamsWang2015OV]. On the hardness side, the conjecture is the source of many tight conditional quadratic lower bounds in string algorithms, geometry, and databases, including for string comparison and dynamic time warping [Bringmann2019FineGrained].

No truly subquadratic algorithm and no unconditional near-quadratic lower bound are known in this dimension regime. The conjecture is open, and refuting it would also refute SETH.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.