Towards a proof of the Fourier-entropy conjecture?
From MaRDI portal
Publication:2216459
DOI10.1007/s00039-020-00544-2zbMath1474.94058arXiv1911.10579OpenAlexW3083257226WikidataQ122938362 ScholiaQ122938362MaRDI QIDQ2216459
Noam Lifshitz, Esty Kelman, Dor Minzer, Shmuel Safra, Guy Kindler
Publication date: 16 December 2020
Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.10579
hypercubepercolationBoolean functionhypercontractivitytotal influencerandom partitionFourier-entropy conjecture
Computational learning theory (68Q32) Measures of information, entropy (94A17) Boolean functions (06E30) Boolean functions (94D10)
Related Items
Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
Cites Work
- Unnamed Item
- Unnamed Item
- Upper bounds on Fourier entropy
- A structure theorem for Boolean functions with small total influences
- On the hardness of approximating minimum vertex cover
- Inequalities in Fourier analysis
- Boolean functions with low average sensitivity depend on few coordinates
- Toward efficient agnostic learning
- Influences of variables and threshold intervals under group symmetries
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- The junta method in extremal hypergraph theory and Chvátal's conjecture
- On the distribution of the Fourier spectrum of Boolean functions
- Nonembeddability theorems via Fourier analysis
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Decision trees, protocols and the entropy-influence conjecture
- The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions
- Intersecting Families are Essentially Contained in Juntas
- Logarithmic Sobolev Inequalities
- Sharp thresholds of graph properties, and the $k$-sat problem
- Learning Decision Trees Using the Fourier Spectrum
- Every monotone graph property has a sharp threshold
- Analysis of Boolean Functions
- A Composition Theorem for the Fourier Entropy-Influence Conjecture
- Reed–Muller Codes Achieve Capacity on Erasure Channels
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
