High frequency criteria for Boolean functions (with an application to percolation)

1 hour 9 mins 7 secs, 63.29 MB, MP3 44100 Hz, 125.02 kbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1123228/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Garban, C (ENS Lyon) Thursday 31 March 2011, 16:30-17:30

Created:

2011-04-04 12:16

Collection:

Discrete Analysis

Publisher:

Isaac Newton Institute

Garban, C

Language:

eng (English)

Distribution:

World

(downloadable)

Credits:

Author:	Garban, C
Director:	Steve Greenham

Explicit content:

Aspect Ratio:

16:9

Screencast:

Bumper:

UCS Default

Trailer:

UCS Default


Abstract:	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 mass'' 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 the kind of techniques we are trying to avoid by looking for a `low cost' criterion. In this talk, I will survey different criteria or techniques which enables one to detect whether a Boolean function is of high frequency or not. To 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 ``small'' (in a precise L^2 way), then the function has to be of high frequency with a quantitative bound on how high the spectrum is. Most of these criteria have been discovered while analyzing the percolation case. Indeed any geometrical event about configurations of percolation can be written as a Boolean function where each ``bit'' determines whether its corresponding edge (or site) is open or closed. It turns out that at criticality, these Boolean functions are of very high frequency. In other words, percolation is very sensitive to small perturbations at the critical point. Since it is very hard to compute all the Fourier coefficients of such functions, 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. Therefore, 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.

Abstract:

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 mass'' 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 the kind of techniques we are trying to avoid by looking for a `low cost' criterion.

In this talk, I will survey different criteria or techniques which enables one to detect whether a Boolean function is of high frequency or not.

To 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 ``small'' (in a precise L^2 way), then the function has to be of high frequency with a quantitative bound on how high the spectrum is.

Most of these criteria have been discovered while analyzing the percolation case. Indeed any geometrical event about configurations of percolation can be written as a Boolean function where each ``bit'' determines whether its corresponding edge (or site) is open or closed. It turns out that at criticality, these Boolean functions are of very high frequency. In other words, percolation is very sensitive to small perturbations at the critical point. Since it is very hard to compute all the Fourier coefficients of such functions, 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.

Therefore, 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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.84 Mbits/sec	961.80 MB	View	Download
WebM	640x360	1.28 Mbits/sec	665.36 MB	View	Download
Flash Video	484x272	568.79 kbits/sec	288.84 MB	View	Download
iPod Video	480x270	506.25 kbits/sec	257.08 MB	View	Download
MP3 *	44100 Hz	125.02 kbits/sec	63.29 MB	Listen	Download
Auto	(Allows browser to choose a format it supports)

Streaming Media Service Upload

High frequency criteria for Boolean functions (with an application to percolation)