Online Orthogonal Vectors Revisited
Abstract
We prove new upper and lower bounds for the Online Orthogonal Vectors Problem (\(\text{OnlineOV}_{n,d}\)). In this problem, a preprocessing algorithm receives \(n\) vectors \(x_1, \ldots, x_n \in \{0,1\}^d\) and constructs a data structure of size \(S\). A query algorithm subsequently receives a query vector \(q \in \{0,1\}^d\) and in time \(T\) decides whether \(q\) is orthogonal to any of the input vectors \(x_i\).
Fields of Study & Subjects
Optimization and Search Problems
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 5641–5668
- Publication date
- 1 January 2026
- Language
- EN