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.