Threshold Functions: Approximation, Pseudorandomness and Learning

Опубликовано 17 августа 2016, 20:31

Abstract: A degree-d threshold function is a boolean function of the form f(x) = sign(p(x)), where p(x) is a degree-d polynomial over the reals. This is a natural and well-studied class of functions that is of fundamental interest in various fields, including complexity theory, machine learning and game theory. We describe recent results on approximating, fooling and learning low-degree threshold functions over the boolean hypercube. In particular, -- We show that any distribution with bounded independence fools the class of degree-2 threshold functions. This yields the first explicit pseudorandom generators against these functions. -- We give the first nontrivial upper bounds on the average sensitivity and noise sensitivity of degree-d threshold functions. This yields the first polynomial-time learning algorithm for this class in the challenging agnostic model. -- We show that any constant-degree threshold function can be approximated by one with small integer weights. The talk will emphasize the connections between these results.