Leírás
Noise-sensitivity of a function on the state space of a Markov chain means that the function decorrelates faster than the relaxation time of the entire system. For iid random input (random walk on the hypercube), discrete Fourier analysis yields a useful theory to understand which functions are noise-sensitive, with great applications, e.g., in percolation theory.
What happens for non-iid input, such as Glauber dynamics for the Ising model or other models of statistical physics, on Euclidean lattices, Cayley graphs of groups, and on random graphs? Or for random walks in permutation groups? Besides discrete Fourier analysis and the complexity theory of Boolean functions, techniques include hypercontractivity, coupling methods, group representation theory. Noise sensitivity also comes up as a possible obstruction for quantum computation.