Correlation Immunity: What, Why, and How Often?

   Eric Bach
   Computer Sciences Department
   University of Wisconsin
   Madison, WI 53706



 Among the n-variable Boolean functions, those with a "balance" property,
called correlation immunity, are of interest in cryptography, coding
theory, and machine learning.  If we think of a function as an arrangement
of 0's and 1's on the hypercube, then it is correlation immune precisely
when the center of mass of this arrangement is at the center of the
hypercube. For certain top-down inference methods that learn from
examples, the functions that are the hardest to learn are exactly those
that are correlation immune.  This property is also useful in designing
stream ciphers to be resistant to certain kinds of cryptanalysis.

   My colleagues Lisa Hellerstein and David Page asked how likely
   it is that a Boolean function is correlation immune, and thus
   hard to learn.  We give this a random walk interpretation, and
   show how earlier asymptotic estimates of Denisov can be
   improved so as to be numerically accurate for very small n.