Towards a proof of the Fourier-entropy conjecture?

DOI10.1007/S00039-020-00544-2zbMATH Open1474.94058arXiv1911.10579OpenAlexW3083257226WikidataQ122938362 ScholiaQ122938362MaRDI QIDQ2216459FDOQ2216459

Authors: Esty Kelman, Noam Lifshitz, Dor Minzer, Guy Kindler, Shmuel Safra 

Publication date: 16 December 2020

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Abstract: The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is $o(logn)$. However, both results become useless when the total influence of the function is $omega(logn)$. The only case in which this logarithmic barrier has been broken for an interesting class of functions was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of $S_n$. In this paper, we build and improve on the techniques of the Bourgain-Kalai paper and establish new concentration results on the Fourier spectrum of Boolean functions with small total influence. Our results include: 1. A quantitative improvement of the Bourgain--Kalai result regarding the total influence of functions that are transitively symmetric. 2. A slightly weaker version of the Fourier--Entropy Conjecture of Friedgut and Kalai. This weaker version implies in particular that the Fourier spectrum of a constant variance, Boolean function $f$ is concentrated on $2^{O(I[f]logI[f])}$ characters, improving an earlier result of Friedgut. Removing the $logI[f]$ factor would essentially resolve the Fourier--Entropy Conjecture, as well as settle a conjecture of Mansour regarding the Fourier spectrum of polynomial size DNF formulas. Our concentration result has new implications in learning theory: it implies that the class of functions whose total influence is at most $K$ is agnostically learnable in time $2^{O(KlogK)}$, using membership queries.

Full work available at URL: https://arxiv.org/abs/1911.10579

Recommendations

• 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
• Improved bounds on Fourier entropy and min-entropy

zbMATH Keywords

hypercubeBoolean functionpercolationhypercontractivitytotal influencerandom partitionFourier-entropy conjecture

Mathematics Subject Classification ID

Computational learning theory (68Q32) Measures of information, entropy (94A17) Boolean functions (06E30) Boolean functions (94D10)

Cites Work

• Learning Decision Trees Using the Fourier Spectrum
• Inequalities in Fourier analysis
• Logarithmic Sobolev Inequalities
• Analysis of Boolean Functions
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• On the hardness of approximating minimum vertex cover
• Boolean functions with low average sensitivity depend on few coordinates
• A structure theorem for Boolean functions with small total influences
• Every monotone graph property has a sharp threshold
• On the distribution of the Fourier spectrum of Boolean functions
• Toward efficient agnostic learning
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Sharp thresholds of graph properties, and the $k$-sat problem
• Intersecting Families are Essentially Contained in Juntas
• Influences of variables and threshold intervals under group symmetries
• Decision trees, protocols and the entropy-influence conjecture
• The Fourier entropy-influence conjecture for certain classes of Boolean functions
• Upper bounds on Fourier entropy
• Title not available (Why is that?)
• Title not available (Why is that?)
• A composition theorem for the Fourier entropy-influence conjecture
• Nonembeddability theorems via Fourier analysis
• The junta method in extremal hypergraph theory and Chvátal's conjecture
• Reed–Muller Codes Achieve Capacity on Erasure Channels

Cited In (11)

• Complexity of quantum circuits via sensitivity, magic, and coherence
• Upper bounds on Fourier entropy
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Sparse reconstruction in spin systems. I: iid spins
• A note on the entropy/influence conjecture
• Upper bounds on Fourier entropy
• On the Fourier spectrum of symmetric Boolean functions
• Strong contraction and influences in tail spaces
• On the \(\Phi \)-stability and related conjectures
• The Fourier entropy-influence conjecture for certain classes of Boolean functions

This page was built for publication: Towards a proof of the Fourier-entropy conjecture?

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