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 fb(S)2. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [24] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C > 0 such that H(f-2) ≤ C · Inf(f), where H(f-2) 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: (i) Our first contribution shows that H(f-2) ≤ 2 · aUC (f), where aUC (f) is the average unambiguous parity-certificate complexity of f. This improves upon several bounds shown by Chakraborty et al. [16]. We further improve this bound for unambiguous DNFs. (ii) We next consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [43, 40] which asks if H∞(f-2) ≤ C · Inf(f), where H∞(f-2) is the min-entropy of the Fourier distribution. We show H∞(f-2) ≤ 2 · C min(f), where C min(f) is the minimum parity certificate complexity of f. We also show that for all ε ≥ 0, we have H∞(f-2) ≤ 2 log(kfbk1,ε/(1 − ε)), where kfbk1,ε is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of read-k DNFs (for constant k). (iii) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3-approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial (whose non-zero Fourier coefficients have the same magnitude) of degree d and sparsity 2ω(d) can 1/3-approximate 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 Bohnenblust-Hille inequality, which has been extensively studied in functional analysis.

Approximate degree, Certificate complexity, FEI conjecture, Fourier analysis of Boolean functions, Polynomial approximation, Query complexity
International Symposium on Theoretical Aspects of Computer Science
Algorithms and Complexity

Arunachalam, S, Chakraborty, S, Koucky, M, Saurabh, N, & de Wolf, R.M. (2020). Improved bounds on Fourier entropy and min-entropy. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020. doi:10.4230/LIPIcs.STACS.2020.45