20211201
Improved bounds on Fourier Entropy and Minentropy
Publication
Publication
ACM Transactions on Computation Theory , Volume 13  Issue 4 p. 1 40
Given a Boolean function f:{ 1,1}n → {1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f (S)2. The Fourier Entropyinfluence (FEI) conjecture of Friedgut and Kalai [28] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C > 0 such that H(f2) ≤ C · Inf (f), where H(f2) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f? In this article, we present three new contributions toward the FEI conjecture: (1) Our first contribution shows that H(f2) ≤ 2 · aUC⊕(f), where a UC⊕(f) is the average unambiguous paritycertificate complexity of f. This improves upon several bounds shown by Chakraborty et al. [20]. We further improve this bound for unambiguous DNFs. We also discuss how our work makes Mansour's conjecture for DNFs a natural next step toward resolution of the FEI conjecture. (2) We next consider the weaker Fourier Minentropyinfluence (FMEI) conjecture posed by O'Donnell and others [50, 53], which asks if H∞ (f2) ≤ C · Inf(f), where H ∞ (f2) is the minentropy of the Fourier distribution. We show H∞(f2) ≤ 2·Cmin⊕(f), where Cmin⊕(f) is the minimum paritycertificate complexity of f. We also show that for all ϵ≥0, we have H∞(f2) ≤ 2 log (f1,ϵ/(1ϵ)), where f1,ϵ is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of readk DNFs (for constant k). (3) 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.
Additional Metadata  

, , , , , , , ,  
doi.org/10.1145/3470860  
ACM Transactions on Computation Theory  
Quantum algorithms and applications  
Organisation  Algorithms and Complexity 
Arunachalam, S, Chakraborty, S, Koucký, M, Saurabh, N, & de Wolf, R.M. (2021). Improved bounds on Fourier Entropy and Minentropy. ACM Transactions on Computation Theory, 13(4), 1–40. doi:10.1145/3470860
