Probabilistic Polynomials and Hamming Nearest Neighbors (Full Version)
Josh Alman, Ryan Williams · 2015
We show how to compute any symmetric Boolean function on n variables over any field (as well as the integers) with a probabilistic polynomial of degree O( √ n log(1/e)) and error at most e . The degree dependence on n and e is optimal, matching a lower bound of Razborov (1987) and Smolensky (1987) for the MAJORITY function. The proof is constructive: a low-degree polynomial can be efficiently sampled from the distribution. This polynomial construction is combined with other algebraic ideas to give the first subquadratic time algorithm for computing a (worst-case) batch of Hamming distances in superlogarithmic dimensions, exactly. To illustrate, let c(n) : N → N. Suppose we are given a database D of n vectors in {0,1}c(n) logn and a collection of n query vectors Q in the same dimension. For all u ∈ Q, we wish to compute a v ∈ D with minimum Hamming distance from u. We solve this problem in n2−1/O(c(n) log2 c(n)) randomized time. Hence, the problem is in “truly subquadratic” time for O(logn) dimensions, and in subquadratic time for d = o((log2 n)/(loglogn)2). We apply the algorithm to computing pairs with maximum inner product, closest pair in l1 for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients. ∗Computer Science Department, Stanford University. Supported by NSF CCF-1212372 and NSF DGE-114747 †Computer Science Department, Stanford University, [email protected]. Supported in part by a David Morgenthaler II Faculty Fellowship, and NSF CCF-1212372. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.