Back to Search Start Over

Upper bounds on Fourier entropy

Authors :
Nitin Saurabh
Raghav Kulkarni
Sourav Chakraborty
Satyanarayana V. Lokam
Source :
Computing and Combinatorics, 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings
Publication Year :
2016
Publisher :
Elsevier BV, 2016.

Abstract

Given a function \(f : {\{0,1\}}^n\rightarrow \mathbb {R}\), its Fourier Entropy is defined to be \(-\sum _S {\widehat{f}}^2(S) \log {\widehat{f}}^2(S)\), where \(\hat{f}\) 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 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.

Details

ISSN :
03043975
Volume :
654
Database :
OpenAIRE
Journal :
Theoretical Computer Science
Accession number :
edsair.doi...........233842215e71899863971085f9e20718