Improved bounds on Fourier entropy and min-entropy

DOI10.1145/3470860MaRDI QIDQ5066141zbMATH OpenOpenAlexFDO

Authors Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf

Publication date 29 March 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.09819, https://ir.cwi.nl/pub/31057

zbMATH Keywords

approximate degreecertificate complexityDNFsentropyFEI conjectureFourier analysis of Boolean functionsMansour's conjecturepolynomial approximationquery complexity

Mathematics Subject Classification ID

Probabilistic methods for one variable harmonic analysis (42A61) Communication complexity, information complexity (68Q11) Boolean functions (94D10)

Abstract: Given a Boolean function $f:{-1,1}^{n}o-1,1$, the Fourier distribution assigns probability $widehatf(S{)}^2$ to $Ssubseteq[n]$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai asks if there exist a universal constant C>0 such that $H(hat{f}^2)leqCInf(f)$, where $H(hat{f}^2)$ is the Shannon entropy of the Fourier distribution of $f$ and $Inf(f)$ is the total influence of $f$. 1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture. This asks if $H_{infty}(hat{f}^2)leqCInf(f)$, where $H_{infty}(hat{f}^2)$ is the min-entropy of the Fourier distribution. We show $H_{infty}(hat{f}^2)leq2C_{min}^{o}plus(f)$, where $C_{min}^{o}plus(f)$ is the minimum parity certificate complexity of $f$. We also show that for every $epsilongeq0$, we have $H_{infty}(hat{f}^2)leq2log(|hatf{|}_{1,epsilon}/(1-epsilon))$, where $|hatf{|}_{1,epsilon}$ is the approximate spectral norm of $f$. As a corollary, we verify the FMEI conjecture for the class of read-$k$ $DNF$s (for constant $k$). 2) We show that $H(hat{f}^2)leq2aU{C}^{o}plus(f)$, where $aU{C}^{o}plus(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(hat{f}^2)leqCmin{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^{omega(d)}$ can 1/3-approximate a Boolean function. We prove this conjecture unconditionally for a particular class of polynomials.

Recommendations

• A composition theorem for the Fourier entropy-influence conjecture
• Upper bounds on Fourier entropy
• Upper bounds on Fourier entropy
• Fourier entropy influence conjecture for random linear threshold functions
• Decision trees, protocols and the entropy-influence conjecture

Cited in

(22)

• Towards a proof of the Fourier-entropy conjecture?
• Proving the conjecture of O'Donnell in certain cases and disproving its general validity
• Fourier entropy influence conjecture for random linear threshold functions
• An improvement of the Feng-Rao bound on minimum distance
• Improved bounds for the complex polynomial Bohnenblust-Hille inequality
• Decision trees, protocols and the entropy-influence conjecture
• The Fourier entropy-influence conjecture for certain classes of Boolean functions
• Upper bounds on Fourier entropy
• Upper bounds on Fourier entropy
• A composition theorem for the Fourier entropy-influence conjecture
• Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
• Improved Bounds on Fourier Entropy and Min-Entropy
• Intermediate classes of nuclear multilinear operators
• On the \(\Phi \)-stability and related conjectures
• Learning low-degree quantum objects
• Characterizing the growth of the anisotropic Bohnenblust-Hille constants
• The sharp constants in the real anisotropic Littlewood's 4/3 inequality and applications
• Boolean functions and Bonami's lemma
• A new bound for the Fourier-entropy-influence conjecture
• A lower bound on the constant in the Fourier min-entropy/influence conjecture
• A note on the entropy/influence conjecture
• A note on the FMEI of the Boolean functions in the generalized Maiorana-McFarland construction

This page was built for publication: Improved bounds on Fourier entropy and min-entropy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066141)