文章基本信息
- 标题：Real Advantage
- 本地全文：下载
- 作者：Alexander Razborov ; Emanuele Viola
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2012
- 卷号：2012
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
We highlight the challenge of proving correlation boundsbetween boolean functions and integer-valued polynomials,where any non-boolean output counts against correlation.
We prove that integer-valued polynomials of degree 21log2log2n have correlation with parity at mostzero. Such a result is false for modular and thresholdpolynomials. Its proof is based on a variant of ananti-concentration result by Costello, Tao, and Vu (DukeMath.~J. 2006).
