Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR12-134 | 27th December 2012 14:25

Revision #1
Authors: Alexander Razborov, Emanuele Viola
Accepted on: 27th December 2012 14:25
Keywords:

Abstract:

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

Changes to previous version:

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.

### Paper:

TR12-134 | 22nd October 2012 23:45

TR12-134
Authors: Alexander Razborov, Emanuele Viola
Publication: 22nd October 2012 23:45
Keywords:

Abstract:

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

ISSN 1433-8092 | Imprint