We present a deterministic, truly subquadratic algorithm for offline (1+epsilon)-approximate nearest or farthest neighbor search (in particular, the closest pair or diameter problem) in Hamming space in any dimension d < n^delta, for a sufficiently small constant delta > 0. The running time of the algorithm is roughly n^{2-epsilon^{1/2+O(delta)}} for nearest neighbors, or n^{2-Omega(sqrt{epsilon}/log(1/epsilon))} for farthest. The algorithm follows from a simple combination of expander walks, Chebyshev polynomials, and rectangular matrix multiplication.
We also show how to eliminate errors in the previous Monte Carlo randomized algorithm of Alman, Chan, and Williams [FOCS'16] for offline approximate nearest or farthest neighbors, and obtain a Las Vegas randomized algorithm with expected running time n^{2-Omega(epsilon^{1/3}/log(1/epsilon))}.
Finally, we note a simplification of Alman, Chan, and Williams' method and obtain a slightly improved Monte Carlo randomized algorithm with running time n^{2-Omega(epsilon^{1/3}/log^{2/3}(1/epsilon))}.
As one application, we obtain improved deterministic and randomized (1+epsilon)-approximation algorithms for MAX-SAT.
We apply the polynomial method---specifically, Chebyshev polynomials---to obtain a number of new results on geometric approximation algorithms in low constant dimensions. For example, we give an algorithm for constructing epsilon-kernels (coresets for approximate width and approximate convex hull) in close to optimal time O(n + (1/epsilon)^{(d-1)/2}), up to a small near-(1/epsilon)^{3/2} factor, for any d-dimensional n-point set. We obtain an improved data structure for Euclidean approximate nearest neighbor search with close to O(n log n + (1/epsilon)^{d/4}n) preprocessing time and O((1/epsilon)^{d/4} log n) query time. We obtain improved approximation algorithms for discrete Voronoi diagrams, diameter, and bichromatic closest pair in the L_s-metric for any even integer constant s > 2. The techniques are general and may have further applications.
We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous constructions, polynomial threshold functions (PTFs) with "nice" threshold behavior and degree almost as low as the probabilistic polynomials, and a new notion of probabilistic PTFs where we combine the above techniques to achieve even lower degree with similar "nice" threshold behavior. Utilizing these polynomial constructions, we design faster algorithms for a variety of problems:
We show how to solve all-pairs shortest paths on n nodes in deterministic n^3 / 2^{Omega(sqrt{log n})} time, and how to count the pairs of orthogonal vectors among n 0-1 vectors in d = c log n dimensions in deterministic n^{2 - 1/O(log c)} time. These running times essentially match the best known randomized algorithms of (Williams, STOC'14) and (Abboud, Williams, and Yu, SODA 2015) respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to count k-SAT assignments on n variable formulas in 2^{n - n/O(k)} time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam (2013).
A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, applying epsilon-biased sets and modulus-amplifying polynomials.
The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.