BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:High frequency criteria for Boolean functions (with an application
  to percolation) - Garban\, C (ENS Lyon)
DTSTART:20110331T153000Z
DTEND:20110331T163000Z
UID:TALK30495@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Assume you are given a certain Boolean function f: {0\,1}^n ->
  {0\,1} and you are suspecting that it is a ``high frequency'' one. It is 
 a non-trivial problem to localize at a `low cost' where the ``Spectral mas
 s'' lies. Of course\, one could compute the Fourier-Walsh coefficients one
  at a time\, but in the generic case this would take forever and this is t
 he kind of techniques we are trying to avoid by looking for a `low cost' c
 riterion. \n\nIn this talk\, I will survey different criteria or technique
 s which enables one to detect whether a Boolean function is of high freque
 ncy or not. \n\nTo give an example of such a criterion\, the first result 
 in this direction is due to Benjamini\, Kalai and Schramm. It states that 
 if the Boolean function f is such that its individual influences are ``sma
 ll'' (in a precise L^2 way)\, then the function has to be of high frequenc
 y with a quantitative bound on how high the spectrum is. \n\nMost of these
  criteria have been discovered while analyzing the percolation case. Indee
 d any geometrical event about configurations of percolation can be written
  as a Boolean function where each ``bit'' determines whether its correspon
 ding edge (or site) is open or closed. It turns out that at criticality\, 
 these Boolean functions are of very high frequency. In other words\, perco
 lation is very sensitive to small perturbations at the critical point. Sin
 ce it is very hard to compute all the Fourier coefficients of such functio
 ns\, several tools have been developed in the literature to understand the
  Fourier spectrum of percolation. Interestingly\, most of these tools can 
 be simply stated and are not specifically designed for percolation. \n\nTh
 erefore\, the purpose of this talk will be to expose these criteria in an 
 accessible way\, with the hope that some of them could be used elsewhere.\
 n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR