Gábor Pete: Open problems related to noise sensitivity and mixing times

Speaker: Gábor Pete

Title: Open problems related to noise sensitivity and mixing times

Abstract: Originally (Benjamini, Kalai & Schramm 1998), a sequence {f_n} of Boolean functions of n iid random input bits is called noise sensitive if, for any \eps>0, resampling each input bit with probability \eps makes the output asymptotically unpredictable, as n\to\infty. This has a simple description in terms of discrete Fourier analysis: f_n is asymptotically uncorrelated with any bounded degree polynomial of the input bits. Nevertheless, there are interesting functions whose noise sensitivity is not known, and there are interesting questions regarding the structure of the Fourier spectrum of Boolean functions. Moreover, noise sensitivity has a natural extension to functions of non-iid input bits, perturbed by some natural Markov chain: e.g., Glauber dynamics for the Ising model, or random walk on the symmetric group with respect to some generating set, with the functions describing some macroscopic observable, such as the majority of the Ising spins, or the existence of large cycles in the permutation.