The main conjecture from Talagrand’s paper on boundaries and influences was settled by Ronen Eldan and Renan Gross. Their paper introduces a new powerful method to the field of analysis of Boolean functions (ABF).
This post is devoted to a new breakthrough paper by Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.
The paper introduces remarkable new techniques based on stochastic calculus, (that bypass the use of hypercontractivity), that allow to settles several open problems on analysis of Boolean functions. (And on the way, to give a very different proof for KKL.)
Renan Gross recently wrote an excellent high-level explanation of the paper in his blog: New paper on arXiv: Concentration on the Boolean hypercube via pathwise stochastic analysis. It is accompanied by a brief introduction to Boolean analysis, featuring the required Boolean material:
Before we move on, a trivia question:
Trivia question: Who invented the term hypercontractivity?
(For a hint, see at the end of the post.)
Back to the paper by Ronen Eldan and Renan Gross. Perhaps the best way to explain what was achieved in this paper is to put one after the other the abstracts of the first version followed by the abstract of the second paper.
Ronen and Renan’s paper. Version 1, 26 Sept 2019.
The title for version 1 was: Stability of Talagrand’s influence inequality
And here is the abstract:
We strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function
where denote the influence of the -th coordinate. We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial (KKL) inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary. Our proofs rely on new techniques, based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.
Let me say a few words about it. KKL theorem asserts that the maximal influence of a balanced Boolean function is at least . The famous tribe example of Ben-Or and Linial shows that this is tight. The KKL paper gave some statements about other norms of the influence vector and Talagrand’s inequality stated above (from the paper “On Russo’s 0-1 law”) gives a sharp description of the influence vectors. Ronen and Renan found a new method that gave new proofs for KKL’s theorem and the stronger Talagrand’s inequality. This new methods led to new stability result.
Now, lets move to version 2.
Ronen and Renan’s paper: Version 2: 12 Nov 2019,
Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.
Abstract: We develop a new technique for proving concentration inequalities which relate between the variance and influences of Boolean functions. Using this technique, we
1. Settle a conjecture of Talagrand [Tal97] proving that
where is the number of edges at along which changes its value, and is the influence of the -th coordinate.
2. Strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function
We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary.
3. Improve a quantitative relation between influences and noise stability given by Keller and Kindler.
Our proofs rely on techniques based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.
Let me explain in a few words the main inequality that verified a conjecture by Talagrand. For other advances look at the paper itself.
The famous Margulis-Talagrand inequality asserts that
Let me say a little more. Talagrand’s proved in his paper on Influence and boundary asserts that the right hand is a constant only if – the sum of squares of the influences is a constant. He conjectured that we can actually add the square root of to the RHS.
A few remarks:
- For more background see my old post “Nati’s influence“.
- Let me mention that Talagrand’s influence inequality (Equation (1) above) is sharp up to a multiplicative constant. This is shown in a 2015 paper: On the Converse of Talagrand’s Influence Inequality by Saleet Klein, Amit Levi, Muli Safra, Clara Shikhelman, and Yinon Spinka.
- Finding the best constant in KKL’s theorem is a well known challenge. So is the question of understanding balanced Boolean functions on n variables where the maximum influence is . Ehud Friedgit in his paper: Influences in Product Spaces, KKL and BKKKL Revisited, have made important conjectures for such Boolean functions.
- I expect that the new method will have many applications. Ronen Eldan in a paper Second-order bounds on correlations between increasing families, found applicaions to correlation inequalities which I will discuss at some other time.
- See the last part of this post for a description of Talagrand’s various relevant papers.
- Renan Gross is building the BooleanZoo in a similar spirit to the famous complexityZoo.
- I was in the process of writing a post about progress on ABS, mentioning twelve or so papers, apologizing for not mentioning others, promising to write in details about some of the papers, and making further apologetic remarks. But as this large post does not advance let me start with some of the promises.
Hint to the trivia question:
The very same person also coined the terms: Berry’s phase, TKN^2 integers, almost Matthieu, HVZ, Birman-Schwinger, infrared bounds, diamagnetic inequality, Verblunsky coefficient, Maryland model, ultracontractivity, …