Average Sensitivity of Polynomial Threshold Functions
Speaker: Rocco A. Servedio , Columbia University
Date: November 17 2009
Time: 4:15PM to 5:15PM
Location: 32-155
Contact: Be, imbe@mit.edu
Relevant URL:
How many edges of the n-dimensional Boolean hypercube can be sliced by a degree-d polynomial surface? This question can be equivalently stated as "What is the maximum average sensitivity of any degree-d polynomial threshold function?" In 1994 Gotsman and Linial posed this question and gave a conjectured answer: the symmetric function slicing the middle d layers of the Boolean hypercube has the highest average sensitivity of all degree-d polynomial threshold functions.
In this work we give the first non-trivial upper bounds on average sensitivity of degree-d polynomial threshold functions (PTFs), thus making progress toward the Gotsman-Linial conjecture. The conjecture itself remains open.
I will explain the main ideas behind our result and describe some of its applications. These include
* the first polynomial-time agnostic learning algorithm for degree-d polynomial threshold functions;
* the first subexponential-time learning algorithm for AC^0 circuits augmented with arbitrary linear threshold gates; and
* low-weight approximators for degree-d polynomial threshold functions.
Joint work with (various subsets of) Ilias Diakonikolas, Parikshit Gopalan, Prasad Raghavendra, Li-Yang Tan, and Andrew Wan.
See other events that are part of Theory Colloquium 2009/2010
See other events happening in November 2009
