Back to Search
Start Over
Upper bounds on Fourier entropy
- 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.
- Subjects :
- Discrete mathematics
Conjecture
General Computer Science
010102 general mathematics
Fourier inversion theorem
0102 computer and information sciences
01 natural sciences
Theoretical Computer Science
Combinatorics
Binary entropy function
Constant factor
symbols.namesake
Fourier transform
010201 computation theory & mathematics
Maximum entropy probability distribution
symbols
Entropy (information theory)
0101 mathematics
Boolean function
Mathematics
Subjects
Details
- ISSN :
- 03043975
- Volume :
- 654
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi...........233842215e71899863971085f9e20718