Skip to main content

Noise Sensitivity Workshop

01/08/2024 - 01/12/2024
Big Lecture Hall, Rényi Institute


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



Sponsored by the ERC Consolidator Grant "NOISE"


Christophe Garban (Université Lyon 1)
Gábor Pete (Rényi and TU Budapest)

Invited Speakers


Gideon Amir
Rangel Baldasso
Zsolt Bartha
Ferenc Bencs
Márton Borbényi
Péter Csikvári
Ágnes Cs. Kúsz
Pierfrancesco Dionigi
John Fernley
Pál Galicza
Christophe Garban
Subhajit Ghosh
Renan Gross
Malo Hillairet
Johan Jonasson
Gergely Kiss
Gady Kozma
Noam Lifshitz
Balázs Maga
Gábor Pete
Ritvik Radhakrishnan
Balázs Ráth
Jacob Richey
Matthew Roberts
Raphael Rossignol
Jan Swart
Márton Szőke
Ádám Timár
Ekaterina Toropova
András Tóbiás
Hugo Vanneuville