Back to my front
page
ERC Consolidator Grant 772466
NoiseSensitivity Everywhere (NOISE)
Gábor Pete
Alfréd Rényi Institute of Mathematics
February 2018  January 2023
Press release of highlighted projects by the European Research Council, including mine.
Postdoc position open now.
Mathematical summary:
Noisesensitivity of a Boolean function with iid random input bits means that resampling a tiny proportion of the input makes the output unpredictable. This notion arises naturally in computer science, but perhaps the most striking example comes from statistical physics, in large part due to the PI: the macroscopic geometry of planar percolation is very sensitive to noise. This can be recast in terms of Fourier analysis on the hypercube: a function is noise sensitive iff most of its Fourier weight is on “high energy” eigenfunctions of the random walk operator.
This project proposes to use noise sensitivity ideas in three main directions:

Address some outstanding questions in the classical case of iid inputs: universality in critical planar percolation; the FriedgutKalai conjecture on Fourier Entropy vs Influence; noise in First Passage Percolation.

In statistical physics, a key example is the critical planar FKIsing model, with noise being Glauber dynamics. One task is to prove noise sensitivity of the macroscopic structure. A key obstacle is that hypercontractivity of the critical dynamics is not known.

Babai's conjecture says that random walk on any finite simple group, with any generating set, mixes
in time polylogarithmic in the volume. Two key open cases are the alternating groups and the linear groups SL(n, F2). We will approach these questions by first proving fast mixing for certain macroscopic structures. For permutation groups, this is the cycle structure, and it is related to a conjecture of Balint Toth on the interchange process, motivated by a phase transition question in quantum mechanics.
We will also apply ideas of statistical physics to group theory in other novel ways, such as understanding the relation between the first ell2Betti number of a group and its measurable cost, or using random walks in random environment to prove amenability of certain groups.
Project members (present and past):
Ádám Timár (Senior researcher 2019 Rényi)
Percolation processes and unimodular random graphs.
Péter Mester (Parttime senior researcher 2020 Rényi)
Groupinvariant percolation processes.
Caio Alves (PostDoc 2020 Rényi)
Percolation theory, loop soup, random graphs.
Olle Elias (PostDoc 2020 Rényi)
Percolation theory, interlacements.
Ábel Farkas (PostDoc 2018 Rényi)
Fractal percolation, geometric measure theory.
Pál Galicza (PhD student 20142020 CEU, PostDoc 2020 Rényi)
Noise sensitivity of Boolean functions and percolation. Sparse reconstruction in spin systems.
Richárd Patkó (PhD student 20172018 BME)
Representation theory and random walks on groups
Sándor Rokob (PhD student 2018 BME, coadvised with Balázs Ráth)
Random interlacements and Uniform Spanning Forests
Mahefa Ravelonanosy (MSc student 2020 CEU, Research intern 2020 Rényi)
Concentration of distances in graph sequences
Gergő Lukáts (MSc student 2019 BME)
Mixing time of critical Ising Glauber dynamics
Papers and preprints:

Gábor Pete and Ádám Timár.
Finiteenergy infinite clusters without anchored expansion. Bernoulli Journal, 9 pages, to appear. [arXiv:2011.01377 math.PR]

Tom Hutchcroft and Gábor Pete.
Kazhdan groups have cost 1. Inventiones mathematicae, vol. 221 (2020), pages 873891. [arXiv:1810.11015 math.GR] Here is a video from IIAS, Jerusalem, October 2018.

Pál Galicza.
Pivotality versus noise stability for monotone transitive functions. Elect. Comm. Probab., Volume 25 (2020), paper no. 17, 6 pp. [arXiv:1909.05375 math.PR]

Ádám Timár.
Oneended spanning trees in amenable unimodular graphs
. Elect. Comm. Probab., Volume 24 (2019), paper no. 72, 12 pp. [arXiv:1805.10690 math.PR]

Gábor Pete and Ádám Timár.
The Free Uniform Spanning Forest is disconnected in some virtually free groups, depending on the generating set. Preprint, 27 pages. [arXiv:2006.06387 math.PR]

Itai Benjamini and Ádám Timár.
Invariant embeddings of unimodular random planar graphs. Preprint, 19 pages. [arXiv:1910.01614 math.PR]

Ádám Timár.
Unimodular random planar graphs are sofic. Preprint, 14 pages. [arXiv:1910.01307 math.PR]

Richárd Patkó and Gábor Pete.
Mixing time and cutoff phenomenon for the interchange process on dumbbell graphs and the labelled exclusion process on the complete graph. Preprint, 21 pages. [arXiv:1908.09406 math.PR]

Pál Galicza and Gábor Pete.
Sparse reconstruction in spin systems I: iid spins. Preprint, 37 pages. [arXiv:2010.10483 math.PR]

Pál Galicza and Gábor Pete.
Sparse reconstruction in spin systems. Talk slides from Prague Stochastics, August 2019.

Ábel Farkas.
Conditional measure on the Brownian path and other random sets. Preprint, 89 pages. [arXiv:1704.05745 math.PR]

Ábel Farkas, Jonathan M. Fraser, Erez Nesharim, David Simmons.
Schmidt's game on Hausdorff metric and function spaces: generic dimension of sets and images. Preprint, 20 pages. [arXiv:1907.07394 math.MG]

Péter Mester.
A factor of i.i.d with uniform marginals and infinite clusters spanned by equal labels. Preprint, 9 pages. [arXiv:1111.3067v2 math.PR]