New and Improved Concrete Lower Bounds for Orthogonal Vectors

Tameem Choudhury, Nutan Limaye, Karteek Sreenivasaiah +1

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$…