ECCC-Report TR12-134https://eccc.weizmann.ac.il/report/2012/134Comments and Revisions published for TR12-134en-usThu, 27 Dec 2012 14:25:44 +0200
Revision 1
| Real Advantage |
Alexander Razborov,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2012/134#revision1We 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).Thu, 27 Dec 2012 14:25:44 +0200https://eccc.weizmann.ac.il/report/2012/134#revision1
Paper TR12-134
| Real Advantage |
Alexander Razborov,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2012/134We 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).Mon, 22 Oct 2012 23:45:46 +0200https://eccc.weizmann.ac.il/report/2012/134