Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-175 | 4th December 2019 18:53

Matching Smolensky's correlation bound with majority

RSS-Feed




TR19-175
Authors: Emanuele Viola
Publication: 4th December 2019 18:53
Downloads: 263
Keywords: 


Abstract:

We show that there are degree-$d$ polynomials over $\mathbb{F}_{2}$ with
correlation $\Omega(d/\sqrt{n})$ with the majority function on $n$
bits. This matches the $O(d/\sqrt{n})$ bound by Smolensky.



ISSN 1433-8092 | Imprint