Presented By: Probability and Analysis Seminar - Department of Mathematics
Small Moments of the Sensitivity of Polynomial Threshold Functions
Chun-Kai Tseng
Abstract: Polynomial threshold functions (PTFs) are a central class of Boolean functions with important roles in learning theory and approximation. A fundamental question is to understand the complexity of their behavior under small perturbations of the input. On the Boolean cube, this is captured by notions such as sensitivity, average sensitivity, and Boolean surface area. In this talk, we revisit a recursive approach used to derive bounds for the average sensitivity and Boolean surface area of PTFs and obtain a polylogarithmic bound for small moments of their sensitivity. We will also explore the interplay between Fourier expansion and induction on scales from harmonic analysis, random averaging from probability, and decision trees and regularization from combinatorics.