Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR19-175 | 4th December 2019 18:53

#### Matching Smolensky's correlation bound with majority

TR19-175
Authors: Emanuele Viola
Publication: 4th December 2019 18:53
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.