Video of this lecture
| COMPUTER SCIENCE/DISCRETE MATH I | |
| Topic: | Average Sensitivity of Polynomial Threshold Functions |
| Speaker: | Rocco Servedio |
| Affiliation: | Columbia University |
| Date: | Monday, February 22 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
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.
We describe recent work that gives 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.
The talk 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 (under the uniform distribution on the Boolean hypercube);
* 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, Andrew Wan.