Speaker: Yuval Filmus, Technion
Title: Structure of (almost) low-degree Boolean functions
Abstract:
Boolean function analysis studies (mostly) Boolean functions on {0,1}^n.
Two basic concepts in the field are *degree* and *junta*.
A function has degree d if it can be written as a degree d polynomial.
A function is a d-junta if it depends on d coordinates.
Clearly, a d-junta has degree d.
What about the converse (for Boolean functions)?
What if the Boolean function is only *close* to degree d?
The questions above were answered by Nisan-Szegedy, Friedgut-Kalai-Naor, and Kindler-Safra.
We consider what happens when we ask the same questions on different domains.
The domains of interest include the biased Boolean cube, the slice, the Grassmann scheme, the symmetric group, high-dimensional expanders, and others.
Joint work with Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Ferdinand Ihringer.