A structure theorem for Boolean functions with small total influences

DOI10.4007/ANNALS.2012.176.1.9zbMath1253.05128arXiv1008.1021OpenAlexW2963226739MaRDI QIDQ447936

Hamed Hatami

Publication date: 30 August 2012

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

phase transitioninfluenceBoolean functionthresholdpseudo-junta

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Boolean functions (06E30)

Related Items (19)

On the failure of concentration for the \(\ell_\infty\)-ball ⋮ Boolean functions: influence, threshold and noise ⋮ Noise-stability and central limit theorems for effective resistance of random electric networks ⋮ Around two theorems and a lemma by Lucio Russo ⋮ Hypercontractivity for global functions and sharp thresholds ⋮ A stability result for the cube edge isoperimetric inequality ⋮ Forbidden intersections for codes ⋮ Critical window of the symmetric perceptron ⋮ The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups ⋮ On a biased edge isoperimetric inequality for the discrete cube ⋮ Towards a proof of the Fourier-entropy conjecture? ⋮ Thresholds and expectation-thresholds of monotone properties with small minterms ⋮ The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture ⋮ On the structure of subsets of the discrete cube with small edge boundary ⋮ Random sum-free subsets of abelian groups ⋮ Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems ⋮ Sharp threshold for the Ising perceptron model ⋮ Unnamed Item ⋮ A quantum algorithm for approximating the influences of Boolean functions and its applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Noise stability of functions with low influences: invariance and optimality
• The jackknife estimate of variance
• Boolean functions with low average sensitivity depend on few coordinates
• On Russo's approximate zero-one law
• Influences of variables and threshold intervals under group symmetries
• The influence of variables in product spaces
• Decision Trees and Influences of Variables Over Product Probability Spaces
• On the critical percolation probabilities
• An approximate zero-one law
• Sharp thresholds of graph properties, and the $k$-sat problem
• Hunting for sharp thresholds
• Every monotone graph property has a sharp threshold
• A Class of Statistics with Asymptotically Normal Distribution

This page was built for publication: A structure theorem for Boolean functions with small total influences