Improved Asymptotic Formulas for Counting Correlation Immune Boolean Functions
Eric Bach · SIAM Journal on Discrete Mathematics · 2009
A Boolean function is called correlation immune if every input is independent of the output when the inputs are chosen from a uniform distribution. We show how an asymptotic formula of Denisov, which approximately counts the n-variable correlation immune functions, can be improved so as to be accurate even for fairly small n. We also provide error estimates for our approximations, which Denisov did not do, and show a connection to the behavior of random walks. Such information is useful to designers of machine learning algorithms and stream ciphers.