文章基本信息

标题：Improved Bounds on Fourier Entropy and Min-Entropy
本地全文：下载
作者：Srinivasan Arunachalam ; Sourav Chakraborty ; Michal Kouck{'y 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：45:1-45:19
DOI：10.4230/LIPIcs.STACS.2020.45
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Fourier analysis of Boolean functions; FEI conjecture; query complexity; polynomial approximation; approximate degree; certificate complexity