Improved Asymptotic Formulas for Counting Correlation-Immune Boolean Functions

Abstract

A Boolean function is called correlation immune if every input is independent of the output, when the inputs are chosen from a uniform distribution. Such functions are of interest in machine learning and stream cipher design. 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. Such information is useful to designers of machine learning algorithms, as it indicates how often a greedy algorithm for learning decision trees will fail.