Noise Sensitivity Workshop

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.

HERE IS THE SCHEDULE AND ABSTRACTS. There will be three minicourses:

Renan Gross (Tel Aviv University): Discrete analysis with continuous processes

1. Introduction to Boolean analysis and stochastics
2. Fractional decision trees and the axis-aligned Laplacian
3. Functional inequalities using a Poisson jump process

Noam Lifshitz (Hebrew University): The synergy between hypercontractivity and representation theory

A recently fertile strand of research in Group Theory involves developing non-abelian analogues of classical combinatorial results for arithmetic Cayley graphs. This includes the exploration of properties such as growth, expansion, mixing, diameter, etc. While remarkable progress has been made in the case of normal Cayley graphs (those generated by unions of conjugacy classes) through character theory, the general case remains poorly understood. In this mini-course, I will provide a gentle introduction to our method, which is based on synergizing hypercontractive inequalities in conjunction with dimensional lower bounds from representation theory. Our approach allows us to obtain qualitative generalizations of several results on normal Cayley graphs.

One notable success of our theory is the full resolution of the 1985 Babai--Sos problem on product-free sets in alternating groups. Additionally, our theory has been applied in a series of papers to make progress on various other open problems related to sets that are not too sparse. These include analogues of Polynomial Freiman-Ruzsa, Bogolyubov’s lemma, Roth’s theorem, the Waring problem, essentially sharp estimates for the diameter problem of Cayley graphs over alternating groups whose density is at least exponential in −n, optimal product mixing in compact Lie groups with applications to quantum communication complexity, and bounds on sizes of products of conjugacy classes of alternating groups.

This work is based on joint collaborations with Keevash; Keevash and Minzer; Keller and Sheinfeld; Arunachalam and Girish; Evra and Kindler; and Ellis, Kindler, and Minzer.

Hugo Vanneuville (Université Grenoble): Noise sensitivity, percolation and the pivotal overlap

1. Noise sensitivity and the pivotal set
2. Noise sensitivity of percolation
3. Noise sensitivity away from the independent case: the Ising model

HERE ARE THE GOODBYE WORDS FROM RENAN.

Sponsored by the ERC Consolidator Grant "NOISE"