Real Advantage
Alexander Alexandrovich Razborov, Emanuele Viola · ACM Transactions on Computation Theory · 2013
We highlight the challenge of proving correlation bounds between boolean functions and real-valued polynomials, where any non-boolean output counts against correlation. We prove that real-valued polynomials of degree 1 2 lg 2 lg 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 et al. [2006].