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.

In the Max-k-Diameter problem, we are given a set of points in a metric space, and the goal is to partition the input points into k parts such that the maximum pairwise distance between points in the same part of the partition is minimized.