Given a Boolean function f : { 1 , 1 } n { 1 , 1 } , the Fourier distribution assigns probability f ^ ( S ) 2 to S [ n ] The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai asks if there exist a universal constant C>0 such that H ( f ^ 2 ) C I n f ( f ) where H ( f ^ 2 ) is the Shannon entropy of the Fourier distribution of f and I n f ( f ) is the total influence of f
1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture. This asks if H ( f ^ 2 ) C I n f ( 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 every ε≥ ε 0 , we have H ( f ^ 2 ) 2 log ( 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 D N F s (for constant k ).
2) We show that H ( f ^ 2 ) 2 a U C ( f ) , where a U C ( f ) is the average unambiguous parity certificate complexity of f . This improves upon Chakraborty et al. An important consequence of the FEI conjecture is the long-standing Mansour's conjecture. We show that a weaker version of FEI already implies Mansour's conjecture: is H ( f ^ 2 ) C min { C 0 ( f ) , C 1 ( f ) } ?, where C 0 ( f ) , C 1 ( f ) are the 0- and 1-certificate complexities of f , respectively.
3) We study what FEI implies about the structure of polynomials that 1/3-approximate a Boolean function. We pose a conjecture (which is implied by FEI): no "flat" degree- d polynomial of sparsity 2 ω ( d ) can 1/3-approximate a Boolean function. We prove this conjecture unconditionally for a particular class of polynomials.
Additional Metadata
Series arXiv.org e-Print archive
Citation
Arunachalam, S, Chakraborty, S, Koucky, M, Saurabh, N, & de Wolf, R. M. (2018). Improved bounds on Fourier entropy and Min-entropy. arXiv.org e-Print archive.