Itai Benjamini and Jeremie Brieussel: Noise Sensitivity Meets Group Theory

The final  version of my ICM 2018 paper Three puzzles on mathematics computation and games has been available for some time. (This proceedings’ version, unlike the arXived version has a full list of references.)  In this post I would like to advertise one problem that I mentioned in the paper. You can read more about it in the paper  by Itai Benjamini and  Jeremie Brieussel  Noise sensitivity of random walks on groups and learn about it also from the videotaped lecture by Jeremie. BTW, the name of my ICM paper is a tribute to Avi Wigdeson’s great book Mathematics and Computation (see this post). Click on the title for an  almost final draft of Avi’s book (March, 25, 2019) soon to be published by Princeton University Press. (We are negotiating with Avi on showing here first what the cover of his book will look like.)


The problem of Benjamini and Brieussel and their conjecture


Consider an n-step simple random walk (SRW) X_n on a Cayley graph of a finitely generated infinite group \Gamma. Refresh independently each step with probability \epsilon, to get Y_n from X_n. Are there groups for which at time n the positions X_n and Y_n are asymptotically independent? That is, does the l_1 (total variation) distance between the chain (X_n, Y_n) and two independent copies (X'_n, X''_n) go to 0, as n \to \infty?

Note that on the line \mathbb Z, they are uniformally correlated, and therefore also on any group with a nontrivial homomorphism to \mathbb R, or on any group that has a finite index subgroup with a nontrivial homomorphism to \mathbb R. On the free group and for any non-Liouville group, X_n and Y_n are correlated as well, but for a different reason: both X_n and Y_n have a nontrivial correlation with X_1.

Itai Benjamini and Jeremie Brieussel conjecture that these are the only ways not to be noise sensitive. That is, if a Cayley graph is Liouville and the group does not have a finite index subgroup with a homomorphism to the reals, then the Cayley graph is noise sensitive for the simple random walk. In particular, the Grigorchuk group is noise sensitive for the simple random walk!

A paragraph of philosophical nature from Benjamini and Brieussel’s paper.

“Physically, an ^1-noise sensitive process can somewhat not be observed, since the observation Y^\rho_n does not provide any significant information on the actual output X_n. Speculatively, this could account for the rarity of Liouville groups in natural science. Indeed besides virtually nilpotent ones, all known Liouville groups are genuinely mathematical objects .”

Polytope integrality gap: An update

An update on polytope integrality gap:  In my ICM paper and also in this post  I posed the beautiful problem that I learned from Anna Karlin if for vertex cover for every graph G and every vector of weights, there is an efficient algorithm achieving the “polytope integrality gap”.  Anna Karlin kindly informed me that Mohit Singh got in touch with her after seeing the conjecture on my blog and pointed out that the hope for approximating the polytope integrality gap for vertex cover is unlikely to be possible because of its relationship to fractional chromatic number. Mohit noted that fractional chromatic number is hard to approximate even when it is constant assuming UGC. I still think that  the notion of polytope integrality gap for vertex cover as well as for more general problems is important and worth further study.



This entry was posted in Algebra, Combinatorics, Probability and tagged , , . Bookmark the permalink.

1 Response to Itai Benjamini and Jeremie Brieussel: Noise Sensitivity Meets Group Theory

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s