Computer Science/Discrete Mathematics Seminar II

Boolean function analysis: beyond the Boolean cube (continued)

Boolean function analysis traditionally studies Boolean functions on the Boolean cube, using Fourier analysis on the group Z_2^n. Other domains of interest include the biased Boolean cube, other abelian groups, and Gaussian space. In all cases, the focus is on results which are independent of the dimension.

Recently, Boolean function analysis has expanded in scope to include other domains such as the symmetric group, the "slice", and the Grassmann scheme. The latter has figured in the recent proof of the 2-to-1 conjecture (a step toward the unique games conjecture) by Dinur, Khot, Kindler, Minzer, and Safra.

In this talk, we systematically survey Boolean function analysis beyond the Boolean cube, focusing on two main points of view: association schemes and differential posets. We also highlight work on the slice, which is the most widely studied non-product domain.

Date & Time

March 06, 2018 | 10:30am – 12:30pm

Location

West Building Lecture Hall

Affiliation

Technion