Speaker Ilias Diakonikolas
Host Eyal Lubetzky
Affiliation Columbia University
Date recorded 7 January 2010
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.
©2010 Microsoft Corporation. All rights reserved.