Probabilistic Polynomials and Hamming Nearest Neighbors

Josh Alman, Ryan Williams

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 )})$ an…