The Robust Sensitivity of Boolean Functions

The sensitivity conjecture is one of the central open problems in Boolean complexity. A recent work of Gopalan et al. [CCC 2016] conjectured a robust analog of the sensitivity conjecture, which relates the decay of the Fourier mass of a Boolean function to moments of its sensitivity. We prove the robust sensitivity conjecture in this work with near optimal parameters.

Authors

• Shachar Lovett
• Avishay Tal
• Jiapeng Zhang

Keywords

No keywords are indexed for this paper.