The Planted Orthogonal Vectors Problem

David Kühnemann, Adam Polak, Alon Rosen

In the $k$-Orthogonal Vectors ($k$-OV) problem we are given $k$ sets, each containing $n$ binary vectors of dimension $d=n^{o(1)}$, and our goal is to pick one vector from each set…