Approximate Orthogonal Vectors and Diameter via Regularity Lemma

We develop algorithms for the approximate Orthogonal Vectors (OV) and Diameter problems over the Hamming space. Prior work exhibited an intriguing sharp transition: for approximation factor c=2, the algorithms are simple and run in Õ(nd) time; whereas already for c=2-δ, the best known approach has been to reduce the problems to nearest neighbor search, leading to solutions with runtimes of the form n1+ω(1). Our algorithms solve (2-δ)-approximate OV and Diameter with runtimes of n1+O(δ) and n1+O(√δ), respectively. The improvement also holds for the online (data structure) versions: online OV and Furthest Neighbor Search (FNS). This is the first direct improvement for approximate FNS in the Hamming space since [Goel, Indyk, Varadarajan 2001]. Our approach consists of two key steps. First, we define a "heterogeneous"pseudo-random instance of the problems and prove a structural lemma showing that any such instance is solved by one of three simple algorithms. Second, we develop a specialized regularity lemma that allows one to reduce any arbitrary dataset to such a pseudo-random instance.