Upper Bounds on Fourier Entropy
- Sourav Chakraborty ,
- Raghav Kulkarni ,
- Satya Lokam ,
- Nitin Saurabh
Lecture Notes in Computer Science |
Published by Springer International Publishing
In this paper we give several upper bounds on the Fourier Entropy of Boolean as well as real valued functions. We first give upper bounds on the Fourier Entropy of Boolean functions in terms of several complexity measures that are known to be bigger than the influence. These complexity measures include, among others, the logarithm of the number of leaves and the average depth of a parity decision tree.