Revision #1 Authors: Alexander Razborov, Emanuele Viola

Accepted on: 27th December 2012 14:25

Downloads: 1586

Keywords:

We highlight the challenge of proving correlation bounds

between boolean functions and integer-valued polynomials,

where any non-boolean output counts against correlation.

We prove that integer-valued polynomials of degree $\frac

12 \log_2 \log_2 n$ have correlation with parity at most

zero. Such a result is false for modular and threshold

polynomials. Its proof is based on a variant of an

anti-concentration result by Costello, Tao, and Vu (Duke

Math.~J. 2006).

The proof of the main lemma contained

a gap. In this version we replace it with a weaker "single value" variant that is however sufficient for our main result (the statement of the

latter has not changed). More technical discussion can be found in the last section.

TR12-134 Authors: Alexander Razborov, Emanuele Viola

Publication: 22nd October 2012 23:45

Downloads: 1712

Keywords:

We highlight the challenge of proving correlation bounds

between boolean functions and integer-valued polynomials,

where any non-boolean output counts against correlation.

We prove that integer-valued polynomials of degree $\frac 12

\log_2 \log_2 n$ have zero correlation with parity. Such a

result is false for modular and threshold polynomials.

Its proof is based on a strengthening of an

anti-concentration result by Costello, Tao, and Vu (Duke

Math.~J. 2006).