Structure of Boolean Almost Low Degree Functions on the Biased Cube

Explore the structural properties of Boolean functions on the biased Boolean cube in this 57-minute lecture by Yuval Filmus from the Technion - Israel Institute of Technology. Delve into the FKN theorem and Kindler-Safra theorem, which describe the behavior of functions close to low degree on the standard Boolean cube. Examine how these results extend to the p-biased setting, where functions close to degree 1 are shown to be near-constant or close to a maximum of a small number of coordinates. Investigate similar structural results for higher degrees and their applications to functions on the symmetric group. Learn about ongoing research in this area, including joint work with Irit Dinur and Prahladh Harsha, which aims to characterize the structure of almost low-degree functions in various settings.

Structure Of Boolean Almost Low Degree Functions On The Biased Cube