Online Orthogonal Vectors Revisited

Karthik Gajulapalli, Alexander Golovnev, Samuel King +1

We prove new upper and lower bounds for the Online Orthogonal Vectors Problem (${\mathsf{OnlineOV}}_{n,d}$). In this problem, a preprocessing algorithm receives $n$ vectors $x_1,\ldo…