Improved Asymptotic Formulas for Counting Correlation-Immune Boolean Functions
University of Wisconsin-Madison Department of Computer Sciences
MetadataShow full item record
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.