Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Threshold Functions: Approximation, Pseudorandomness and Learning

Speaker  Ilias Diakonikolas

Affiliation  Columbia University

Host  Eyal Lubetzky

Duration  00:51:56

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.
> Threshold Functions: Approximation, Pseudorandomness and Learning