Threshold Functions: Approximation, Pseudorandomness and Learning

January 7, 2010
Ilias Diakonikolas | Columbia University

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.

Speaker Details

Ilias Diakonikolas received his undergraduate degree in Electrical and Computer Engineering from the National Technical University of Athens. He is currently pursuing a Ph.D. in Computer Science at Columbia University under the supervision of Professor Mihalis Yannakakis.Ilias’ research interests are in theoretical computer science. His thesis work focuses in the development of a coherent algorithmic theory for multiobjective optimization problems. His work in this area has been recently honored by the INFORMS society. Ilias also has strong interests in applied probability, more specifically its intersection with computational complexity, learning and property testing.