Skip to Content

Sponsors

No results

Keywords

No results

Types

No results

Search Results

Events

No results
Search events using: keywords, sponsors, locations or event type
When / Where

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.

Explore Similar Events

  •  Loading Similar Events...

Keywords


Back to Main Content