Fall 2013

Friedgut-Kalai-Naor for Boolean Functions on S_n

Monday, Dec. 2, 2013 4:15 pm5:00 pm PST

Add to Calendar

The classical Friedgut-Kalai-Naor (FKN) theorem states that if most of the Fourier spectrum of a boolean function on {0,1}^n is concentrated on the first two levels then the function essentially depends on one coordinate. We extend this result to boolean functions on S_n whose Fourier spectrum is concentrated on the first two irreducible representations. When the function is balanced, we show that it essentially depends on either the image or the inverse image of one point. When the function is skewed, we show that it is close to a disjunction of double cosets (indicators of events of the type "i maps to j").

Joint work with David Ellis and Ehud Friedgut.