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.

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).