Date
Tue, 05 Feb 2013
Time
14:30 - 15:30
Location
L3
Speaker
David Ellis
Organisation
Queen Mary

Results of Bourgain and Kindler-Safra state that if $f$ is a Boolean function on $\{0,1\}^n$, and

the Fourier transform of $f$ is highly concentrated on low frequencies, then $f$ must be close

to a ‘junta’ (a function depending upon a small number of coordinates). This phenomenon is

known as ‘Fourier stability’, and has several interesting consequences in combinatorics,

theoretical computer science and social choice theory. We will describe some of these,

before turning to the analogous question for Boolean functions on the symmetric group. Here,

genuine stability does not occur; it is replaced by a weaker phenomenon, which we call

‘quasi-stability’. We use our 'quasi-stability' result to prove an isoperimetric inequality

for $S_n$ which is sharp for sets of size $(n-t)!$, when $n$ is large. Several open questions

remain. Joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Weizmann

Institute).

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.