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 #2 to TR20-175 | 10th May 2021 15:14

Fourier conjectures, correlation bounds, and Majority

RSS-Feed




Revision #2
Authors: Emanuele Viola
Accepted on: 10th May 2021 15:14
Downloads: 123
Keywords: 


Abstract:

Recently several conjectures were made regarding the Fourier spectrum of low-degree polynomials. We show that these conjectures imply new correlation bounds for functions related to Majority. Then we prove several new results on correlation bounds which aim to, but don't, resolve the conjectures. In particular, we prove several new results on Majority which are of independent interest and complement Smolensky's classic result.



Changes to previous version:

Multiple bounds improved -- see ack.


Revision #1 to TR20-175 | 23rd December 2020 21:50

Fourier conjectures, correlation bounds, and Majority





Revision #1
Authors: Emanuele Viola
Accepted on: 23rd December 2020 21:50
Downloads: 134
Keywords: 


Abstract:

Recently several conjectures were made regarding the Fourier spectrum of low-degree polynomials. We show that these conjectures imply new correlation bounds for functions related to Majority. Then we prove several new results on correlation bounds which aim to, but don't, resolve the conjectures. In particular, we prove several new results on Majority which are of independent interest and complement Smolensky's classic result.



Changes to previous version:

Added a conjecture about majority


Paper:

TR20-175 | 24th November 2020 17:21

Fourier conjectures, correlation bounds, and Majority





TR20-175
Authors: Emanuele Viola
Publication: 24th November 2020 17:22
Downloads: 423
Keywords: 


Abstract:

Recently several conjectures were made regarding the Fourier spectrum of low-degree polynomials. We show that these conjectures imply new correlation bounds for functions related to Majority. Then we prove several new results on correlation bounds which aim to, but don't, resolve the conjectures. In particular, we prove several new results on Majority which are of independent interest and complement Smolensky's classic result.



ISSN 1433-8092 | Imprint