Detecting the relevant attributes of an unknown target concept
is an important and well studied problem in algorithmic learning.
Simple greedy strategies have been proposed that seem to perform reasonably
well in practice if a sufficiently large random subset of examples of the target
concept is provided.

Introducing a ... more >>>

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$
satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96)\cite{FG96}. The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of ... more >>>