Computer Science

On the correlation of symmetric functions

Jin Yi Cai, University at Buffalo, The State University of New York
F. Green, Clark University
T. Thierauf, Universität Ulm


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 2n. 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 [12] restricted to symmetric Boolean functions: the correlation between parity and any circuit consisting of a Modq 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-Ω(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.