Computer Science/Discrete Mathematics Seminar II

The sensitivity conjecture is a famous open problem in the theory of boolean functions. Let $f$ be a boolean function defined on the hypercube. The sensitivity of a node $x$ is the number of its neighbours in the hypercube, for which $f$ give the opposite value as that it does to $x$. The sensitivity conjecture speculates that if all nodes have low sensitivity, then the function $f$ must be simple. Concretely, all its Fourier mass is supported on levels with low hamming weight. Recently, Gopalan et al [CCC 2016] conjectured a robust analogue of the sensitivity conjecture: if most of the nodes have low sensitivity, then most of the Fourier mass is supported on levels with low hamming weight. They also proved it under the stronger assumption that all nodes have low sensitivity. In this work, we prove this conjecture, with near tight quantitative bounds. We also show the reverse inequality: if most of the Fourier weight is supported on low levels, then most nodes have low senitivity. Thus, this establishes new relations between typical local proerties of a boolean function (sensitivity) and global properties (Fourier coefficients). Joint work with Avishay Tal and Jiapeng Zhang.