# Probabilistic Polynomials and Hamming Nearest Neighbors

arXiv: https://arxiv.org/abs/1507.05106 · HTML: https://mlsanity.com/paper/1507.05106/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jul 2015.

## Built on by (most cited first, 3 of 3)

- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?](https://mlsanity.com/paper/2101.10905/) (2021)
- [Can You Solve Closest String Faster than Exhaustive Search?](https://mlsanity.com/paper/2305.16878/) (2023)

## Abstract (arXiv)

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/ε)) and error at most ε. The degree dependence on n and ε 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) : mathbbN rightarrow mathbbN. Suppose we are given a database D of n vectors in 0,1c(n) log n 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(log n) dimensions, and in subquadratic time for d = o((log2 n)/(log log n)2). We apply the algorithm to computing pairs with maximum inner product, closest pair in ℓ1 for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients.