Probabilistic Polynomials and Hamming Nearest Neighbors

DOI10.1109/FOCS.2015.18arXiv1507.05106MaRDI QIDQ6263712FDOQ6263712

Ryan Williams, Josh Alman

Publication date: 17 July 2015

Abstract: 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(sqrtnlog(1/epsilon))$ and error at most $epsilon$. The degree dependence on $n$ and $epsilon$ 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):mathbbNightarrowmathbbN$. 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 $uinQ$, we wish to compute a $vinD$ with minimum Hamming distance from $u$. We solve this problem in $n^{2-1/O(c(n)lo{g}^{2}c(n))}$ randomized time. Hence, the problem is in "truly subquadratic" time for $O(logn)$ dimensions, and in subquadratic time for $d=o((lo{g}^{2}n)/(loglogn{)}^2)$. We apply the algorithm to computing pairs with maximum inner product, closest pair in $el{l}_1$ for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients.

This page was built for publication: Probabilistic Polynomials and Hamming Nearest Neighbors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6263712)