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 |

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.