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 -step simple random walk (SRW) on a Cayley graph of a finitely generated infinite group . Refresh independently each step with probability , to get from . Are there groups for which at time the positions and are asymptotically independent? That is, does the (total variation) distance between the chain and two independent copies go to 0, as ?
Note that on the line , they are uniformally correlated, and therefore also on any group with a nontrivial homomorphism to , or on any group that has a finite index subgroup with a nontrivial homomorphism to . On the free group and for any non-Liouville group, and are correlated as well, but for a different reason: both and have a nontrivial correlation with .
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 ℓ-noise sensitive process can somewhat not be observed, since the observation does not provide any significant information on the actual output . 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.