Improved Asymptotic Formulas for Counting Correlation-Immune Boolean Functions
File(s)
Date
2007Author
Bach, Eric
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
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.
Permanent Link
http://digital.library.wisc.edu/1793/60596Citation
TR1616