Probabilistic Polynomials and Hamming Nearest Neighbors

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(\sqrt{n\log (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):\mathbb{N}\to \mathbb{N}$. Suppose we are given a database $D$ of $n$ vectors in $\{0,1{\}}^{c(n)\log n}$ and a collection of $n$ query vectors $Q$ in the same dimension. For all $u\in Q$, we wish to compute a $v\in D$ with minimum Hamming distance from $u$. We solve this problem in $n^{2-1/O(c(n){\log }^{2}c(n))}$ randomized time. Hence, the problem is in "truly subquadratic" time for $O(\log n)$ dimensions, and in subquadratic time for $d=o(({\log }^{2}n)/(\log \log n{)}^2)$. We apply the algorithm to computing pairs with maximum inner product, closest pair in ${\ell }_1$ for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients.

16 pages. To appear in 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)

References in corpus (1)

• Optimal Data-Dependent Hashing for Approximate Near Neighbors

Cited by in corpus (26)

• Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
• From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering
• On the Complexity of Inner Product Similarity Join
• Fair Near Neighbor Search: Independent Range Sampling in High Dimensions
• Subquadratic Algorithms for Succinct Stable Matching
• Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
• Impossibility Results for Grammar-Compressed Linear Algebra
• Hybrid LSH: Faster Near Neighbors Reporting in High-dimensional Space
• Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing
• An Illuminating Algorithm for the Light Bulb Problem
• A New Algorithm for Finding Closest Pair of Vectors
• How proofs are prepared at Camelot
• Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
• Probabilistic Rank and Matrix Rigidity
• Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry
• CoveringLSH: Locality-sensitive Hashing without False Negatives
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
• A Robust Version of Hegedűs's Lemma, with Applications
• The PCP-like Theorem for Sub-linear Time Inapproximability
• Fast Unbalanced Optimal Transport on a Tree
• PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability
• On the I/O complexity of the k-nearest neighbor problem
• Algorithms for Similarity Search and Pseudorandomness
• Circuit Depth Reductions
• On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry