Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-161 | 9th January 2017 00:38

Robust sensitivity

RSS-Feed




Revision #1
Authors: Shachar Lovett, Avishay Tal, Jiapeng Zhang
Accepted on: 9th January 2017 00:38
Downloads: 1695
Keywords: 


Abstract:

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 this robust analog in this work.



Changes to previous version:

We optimized the parameter a_{d} from 2^{O(d^{3/2})} to d^{O(d)}


Paper:

TR16-161 | 26th October 2016 22:11

Robust sensitivity





TR16-161
Authors: Shachar Lovett, Jiapeng Zhang
Publication: 26th October 2016 22:39
Downloads: 1906
Keywords: 


Abstract:

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 this robust analog in this work.



ISSN 1433-8092 | Imprint