2026/07/26 by Tameem Choudhury, Nutan Limaye, Karteek Sreenivasaiah +1
#cs.CC
The Orthogonal Vectors Problem (OVn,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 ∈ A and b ∈ B such that a and b are orthogonal. The OV conjecture states that for every ε > 0, there exists a constant c ≥ 1 such that there is no algorithm deciding OVn,d for d = c log n with running time O(n2-ε). The analogous k-OV conjecture hypothesizes a lower bound of nk-ε 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Ω(1). We show that the monotone version of the OV conjecture holds for monotone circuits. More formally, we show that for every ε> 0, there exists c such that any monotone circuit family computing the negation of OVn,d with d=clog n must have size Ω(n2-ε). We also prove stronger Boolean formula and branching program lower bounds for OVn,d, strengthening a previous result of Kane and Williams (ITCS 2019). In particular, our Boolean formula lower bound of Ω(n2 d) is tight up to constant factors.