Paper Info
Title
Upper Bounds on Fourier Entropy.
Abstract
Given a function f:{0,1}n→{+1,−1}, its Fourier Entropy is defined to be −∑Sfˆ(S)2log⁡fˆ(S)2, where fˆ denotes the Fourier transform of f. In the analysis of Boolean functions, an outstanding open question is a conjecture of Friedgut and Kalai, 1996 [3], called the 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.
Year
DOI
Venue
2015
10.1016/j.tcs.2016.05.006
Theoretical Computer Science
Keywords
DocType
Volume
Boolean functions,Fourier entropy,Noise sensitivity,Influence,Read-once formulas,Decision trees,Threshold functions
Conference
654
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Sourav Chakraborty138149.27
Raghav Kulkarni217219.48
Satyanarayana V. Lokam327422.36
Nitin Saurabh453.81