Jin-Yi Cai, Frederic Green, and Thomas Thierauf

**Abstract: **

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.