Average Sensitivity of Polynomial Threshold Functions

Video of this lecture

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
Video Link:https://video.ias.edu/csdm/avgsensitivity

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.