Combinatorics Seminar: Yuval Filmus (Technion) "Structure of (almost) low-degree Boolean functions"

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.

Date: 

2019-03-11 11:00 to 13:00

Location: 

CS bldg, room B500, Safra campus, Givat Ram