University of Cambridge > > Cambridge Analysts' Knowledge Exchange > Noise sensitivity of Boolean functions

Noise sensitivity of Boolean functions

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Martin Taylor.

A Boolean function is a function from the hypercube {-1,1}^n into {-1,1}. Basic examples include the dictatorship function DICT = x_1 and the parity function PAR = x_1...x_n. We consider the effect of perturbing x_1,...,x_n by some small random noise. Clearly one would expect the dictatorship function to remain unchanged and the parity function to be almost independent from before. Our main interest is in Boolean functions arising in the percolation model where the effect of a random noise is less obvious. We shall see that phenomenon of noise sensitivity is related to the energy spectrum of a function. Thus Fourier analysis gives us a powerful tool for studying the affects of random noise on a percolation configuration.

This talk is part of the Cambridge Analysts' Knowledge Exchange series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity