Computer Science/Discrete Mathematics Seminar I

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.