Probabilistic Polynomials for MajoritySpeaker: Josh
Title: Probabilistic Polynomials for Majority
Date: 05 Oct 2020 17:15-18:30 EST (talk starts at 17:30)
Abstract: A probabilistic polynomial with error eps for a Boolean function f is a distribution P on polynomials such that, for every Boolean input x, there is a 1-eps chance that when you draw a polynomial p from P, it satisfies p(x) = f(x). I will show a matching upper and lower bound for the degree required for the Majority function on n inputs. I will then show that the lower bound has applications to circuit complexity, and the upper bound has applications to nearest neighbor search algorithms. It should be fun!