Fourier Conjectures, Correlation Bounds, and Majority
Chattopadhyay, Eshan, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek S. Shetty · arXiv (Cornell University) · 2020
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.