摘要：Given a Boolean function f:{-1,1}â¿â' {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S âS [n] is sampled with probability fÌ,(S)². The Fourier Entropy-Influence (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^âS.(f), where aUC^âS.(f) is the average unambiguous parity-certificate 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 Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [R. O'Donnell et al., 2011; R. O'Donnell, 2014] which asks if â"_{â^Z}(fÌ,²) ⤠Câ<. Inf(f), where â"_{â^Z}(fÌ,²) is the min-entropy of the Fourier distribution. We show â"_{â^Z}(fÌ,²) ⤠2â<.ð-¢_{min}^âS.(f), where ð-¢_{min}^âS.(f) is the minimum parity certificate complexity of f. We also show that for all ε ⥠0, we have â"_{â^Z}(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 read-k DNFs (for constant k). iv) 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.
