Orthogonal Vectors Conjecture

For positive integers $n$ and $m$, let $\emph{\textsf{OV}}(n,m)$ denote the Orthogonal Vectors problem: given sets $A=\{x^{(1)},\ldots,x^{(n)}\}$ and $B=\{y^{(1)},\ldots,y^{(n)}\}\subset\{0,1\}^m$, determine whether there are $i,j\in[n]$ with $\langle x^{(i)}-y^{(j)}\rangle=0$. Orthogonal Vectors Conjecture. For every $\delta>0$, there is $c\ge 1$ such that $\emph{\textsf{OV}}(n,m)$ cannot be solved in $O(n^{2-\delta})$ time on instances with $m=c\log n$. This conjecture is a standard source of conditional fine-grained lower bounds, including reductions to kernel density estimation; its resolution status is not specified in the input.