New and Improved Concrete Lower Bounds for Orthogonal Vectors

Abstract

The Orthogonal Vectors Problem (OV${}_{n,d}$) takes as input two sets $A,B$ each containing $n$ $d$-dimensional Boolean vectors, and outputs $1$ if and only if there exists $a\in A$ and $b\in B$ such that $a$ and $b$ are orthogonal. The OV conjecture states that for every $\epsilon >0$, there exists a constant $c\ge 1$ such that there is no algorithm deciding OV${}_{n,d}$ for $d=c\log n$ with running time $O(n^{2-\epsilon })$. The analogous $k$-OV conjecture hypothesizes a lower bound of $n^{k-\epsilon }$ for the same problem with $k$ sets. We prove these results and variants unconditionally in concrete computational models. We study a natural monotone version of the $k$-OV conjecture and shows that it holds for monotone circuits and constant-depth (not necessarily monotone) circuits when $d=n^{\Omega (1)}.$ We show that the monotone version of the OV conjecture holds for monotone circuits. More formally, we show that for every $\epsilon >0$, there exists $c$ such that any monotone circuit family computing the negation of OV${}_{n,d}$ with $d=c\log n$ must have size $\Omega (n^{2-\epsilon })$. We also prove stronger Boolean formula and branching program lower bounds for OV${}_{n,d}$, strengthening a previous result of Kane and Williams (ITCS 2019). In particular, our Boolean formula lower bound of $\Omega (n^{2}d)$ is tight up to constant factors.