Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Real Advantage

RSS-Feed




Revision #1
Authors: Alexander Razborov, Emanuele Viola
Accepted on: 27th December 2012 14:25
Downloads: 2872
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

Real Advantage





TR12-134
Authors: Alexander Razborov, Emanuele Viola
Publication: 22nd October 2012 23:45
Downloads: 3020
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