Probabilistic Polynomials and Hamming Nearest Neighbors
summary
Claims an offline algorithm for n batch Hamming nearest neighbors that is truly subquadratic when d = c log n: time n^{2 - 1/O(c log^2 c)} for constant c, by reducing the problem to many small s-sized subproblems and evaluating a low‑monomial polynomial on all group pairs. Key tools are probabilistic polynomials for threshold/majority with degree Θ(√(d log 1/ε)) and fast rectangular matrix multiplication to evaluate few‑monomial polynomials on many points. Gives one‑sided error amplification and a SETH‑based barrier showing limited further improvement.
AI-written summary · about
chapters (9)
- 0:00Intro
- 1:31Hamming Nearest Neighbor Problem: Past Work
- 4:13Batch Hamming Nearest Neighbor Problem: Our Result
- 14:51Probabilistic Polynomials for MAJORITY
- 17:25THRESHOLD: Recursive Intuition
- 20:13From Probabilistic Polynomial to Hamming Distance Algorithm
- 26:24Solving Batch Hamming Nearest Neighbor
- 26:55Hamming distance problem polynomial = algorithm
- 29:59Hamming distance problem algorithm = Batch Hamming nearest neighbor