Polynomial Representations of Threshold Functions and Algorithmic Applications

Josh Alman, Timothy M. Chan, Ryan Williams

We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous con…