Arunachalam, Srinivasan ;
Chakraborty, Sourav ;
Koucký, Michal ;
Saurabh, Nitin ;
de Wolf, Ronald
Improved Bounds on Fourier Entropy and MinEntropy
Abstract
Given a Boolean function f:{1,1}ⁿ→ {1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f̂(S)². The Fourier EntropyInfluence (FEI) conjecture of Friedgut and Kalai [E. Friedgut and G. Kalai, 1996] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C>0 such that ℍ(f̂²)≤ C⋅ Inf(f), where ℍ(f̂²) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f?
In this paper we present three new contributions towards the FEI conjecture:
ii) Our first contribution shows that ℍ(f̂²) ≤ 2⋅ aUC^⊕(f), where aUC^⊕(f) is the average unambiguous paritycertificate complexity of f. This improves upon several bounds shown by Chakraborty et al. [S. Chakraborty et al., 2016]. We further improve this bound for unambiguous DNFs.
iii) We next consider the weaker Fourier MinentropyInfluence (FMEI) conjecture posed by O'Donnell and others [R. O'Donnell et al., 2011; R. O'Donnell, 2014] which asks if ℍ_{∞}(f̂²) ≤ C⋅ Inf(f), where ℍ_{∞}(f̂²) is the minentropy of the Fourier distribution. We show ℍ_{∞}(f̂²) ≤ 2⋅𝖢_{min}^⊕(f), where 𝖢_{min}^⊕(f) is the minimum parity certificate complexity of f. We also show that for all ε ≥ 0, we have ℍ_{∞}(f̂²) ≤ 2log (‖f̂‖_{1,ε}/(1ε)), where ‖f̂‖_{1,ε} is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of readk DNFs (for constant k).
iv) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial (whose nonzero Fourier coefficients have the same magnitude) of degree d and sparsity 2^ω(d) can 1/3approximate a Boolean function. This conjecture is known to be true assuming FEI and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We discuss an intriguing connection between our conjecture and the constant for the BohnenblustHille inequality, which has been extensively studied in functional analysis.
BibTeX  Entry
@InProceedings{arunachalam_et_al:LIPIcs:2020:11906,
author = {Srinivasan Arunachalam and Sourav Chakraborty and Michal Kouck{\'y} and Nitin Saurabh and Ronald de Wolf},
title = {{Improved Bounds on Fourier Entropy and MinEntropy}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {45:145:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771405},
ISSN = {18688969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11906},
URN = {urn:nbn:de:0030drops119062},
doi = {10.4230/LIPIcs.STACS.2020.45},
annote = {Keywords: Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity}
}
04.03.2020
Keywords: 

Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity 
Seminar: 

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Issue date: 

2020 
Date of publication: 

04.03.2020 