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].
No takes yet. Share an insight, caveat, or question.
Razborov et al. (2013) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: