On the Correlation of Symmetric Functions

Jin-Yi Cai, Frederic Green, and Thomas Thierauf

The correlation between two Boolean functions of n inputs is defined as the number of times the functions agree minus the number of times they disagree, all divided by 2^n. In this paper, we compute, in closed form, the correlation between any two symmetric Boolean functions. As a consequence of our main result, we get that every symmetric Boolean function having an odd period has an exponentially small correlation (in n) with the parity function. This improves a result of Smolensky restricted to symmetric Boolean functions: the correlation between parity and any circuit consisting of a Mod_q gate over AND-gates of small fan-in, where q is odd and the function computed by the sum of the AND-gates is symmetric, is bounded by 2^{-\Omega(n)}.

In addition, we find that for a large class of symmetric functions the correlation with parity is identically zero for infinitely many n. We characterize exactly those symmetric Boolean functions having this property.