Date: August 24, 2026
Title: Online Orthogonal Vectors Revisited
Speaker: Alexander Golovnev, Associate Professor, Cornell University
Abstract: We prove new upper and lower bounds for the Online Orthogonal Vectors Problem (OnlineOV). In this problem, a preprocessing algorithm receives n vectors and constructs a data structure of size S. Subsequently, a query algorithm receives a vector q and, in time T, determines whether q is orthogonal to any of the input vectors.
Using a novel structure-versus-randomness decomposition, we design data structures that outperform all known constructions and refute a conjecture regarding the hardness of OnlineOV. On the lower-bound side, assuming the Non-uniform Strong Exponential Time Hypothesis, we prove arbitrarily large polynomial lower bounds on the space S required by any OnlineOV data structure with computationally unbounded preprocessing and sublinear query time.