Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-052 | 4th April 2013 05:51

Upper Bounds on Fourier Entropy

RSS-Feed




Revision #1
Authors: Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh
Accepted on: 4th April 2013 05:51
Downloads: 1277
Keywords: 


Abstract:

Given a function $f : \{0,1\}^n \to \reals$, its {\em Fourier Entropy} is defined to be $-\sum_S \fcsq{f}{S} \log \fcsq{f}{S}$, where $\fhat$ denotes the Fourier transform of $f$. This quantity arises in a number of applications, especially in the study of Boolean functions. An outstanding open question is a conjecture of Friedgut and Kalai (1996), called Fourier Entropy Influence (FEI) Conjecture, asserting that the Fourier Entropy of any Boolean function $f$ is bounded above,
up to a constant factor, by the total influence (= average sensitivity) of $f$.

In this paper we give several upper bounds on the Fourier Entropy of Boolean as well as
real valued functions. We give a general bound involving the $(1+\delta)$-th moment of $|S|$ w.r.t. the distribution $\fcsq{f}{S}$; the FEI conjecture needs the first moment of $|S|$. A variant of this bound uses the first and second moments of sensitivities (average sensitivity being the first moment). We also 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 decision tree. Finally, we show that the FEI Conjecture holds for two special classes of functions, namely linear threshold functions and read-once formulas.



Changes to previous version:

A curly bracket from the title is removed.


Paper:

TR13-052 | 3rd April 2013 10:18

{Upper Bounds on Fourier Entropy





TR13-052
Authors: Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh
Publication: 3rd April 2013 23:01
Downloads: 1342
Keywords: 


Abstract:

iven a function $f : \{0,1\}^n \to \reals$, its {\em Fourier Entropy} is defined to be $-\sum_S \fcsq{f}{S} \log \fcsq{f}{S}$, where $\fhat$ denotes the Fourier transform of $f$. This quantity arises in a number of applications, especially in the study of Boolean functions. An outstanding open question is a conjecture of Friedgut and Kalai (1996), called Fourier Entropy Influence (FEI) Conjecture, asserting that the Fourier Entropy of any Boolean function $f$ is bounded above,
up to a constant factor, by the total influence (= average sensitivity) of $f$.

In this paper we give several upper bounds on the Fourier Entropy of Boolean as well as
real valued functions. We give a general bound involving the $(1+\delta)$-th moment of $|S|$ w.r.t. the distribution $\fcsq{f}{S}$; the FEI conjecture needs the first moment of $|S|$. A variant of this bound uses the first and second moments of sensitivities (average sensitivity being the first moment). We also 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 decision tree. Finally, we show that the FEI Conjecture holds for two special classes of functions, namely linear threshold functions and read-once formulas.



ISSN 1433-8092 | Imprint