Improved bounds on Fourier entropy and min-entropy

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.

• View at Publisher

Full Text ( Final Version , 612kb )

See Also
article Improved bounds on Fourier Entropy and Min-entropy S. Arunachalam (Srinivasan), S. Chakraborty (Sourav), M. Koucký (Michal), N. Saurabh (Nitin) and R.M. de Wolf (Ronald)