A structure theorem for Boolean functions with small total influences
From MaRDI portal
Publication:447936
DOI10.4007/ANNALS.2012.176.1.9zbMATH Open1253.05128arXiv1008.1021OpenAlexW2963226739MaRDI QIDQ447936FDOQ447936
Authors: Hamed Hatami 
Publication date: 30 August 2012
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Abstract: We show that on every product probability space, Boolean functions with small total influences are essentially the ones that are almost measurable with respect to certain natural sub-sigma algebras. This theorem in particular describes the structure of monotone set properties that do not exhibit sharp thresholds. Our result generalizes the core of Friedgut's seminal work [Ehud Friedgut. Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc., 12(4):1017-1054, 1999.] on properties of random graphs to the setting of arbitrary Boolean functions on general product probability spaces, and improves the result of Bourgain in his appendix to Friedgut's paper.
Full work available at URL: https://arxiv.org/abs/1008.1021
Recommendations
- The Fourier entropy-influence conjecture for certain classes of Boolean functions
- Approximation of biased Boolean functions of small total influence by DNFs
- On the complexity of Boolean functions with small number of ones
- Boolean functions with small spectral norm, revisited
- scientific article; zbMATH DE number 1962825
- On the power of choice for Boolean functions
- Boolean functions with small spectral norm
- A lower bound for the affinity level for almost all Boolean functions
Cites Work
- The jackknife estimate of variance
- A Class of Statistics with Asymptotically Normal Distribution
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Boolean functions with low average sensitivity depend on few coordinates
- On Russo's approximate zero-one law
- The influence of variables in product spaces
- Decision Trees and Influences of Variables Over Product Probability Spaces
- Every monotone graph property has a sharp threshold
- On the critical percolation probabilities
- Noise stability of functions with low influences: invariance and optimality
- Sharp thresholds of graph properties, and the $k$-sat problem
- Influences of variables and threshold intervals under group symmetries
- Title not available (Why is that?)
- An approximate zero-one law
- Title not available (Why is that?)
- Hunting for sharp thresholds
Cited In (29)
- Forbidden intersections for codes
- On the failure of concentration for the \(\ell_\infty\)-ball
- Noise-stability and central limit theorems for effective resistance of random electric networks
- Boolean functions: influence, threshold and noise
- Approximation of biased Boolean functions of small total influence by DNFs
- Random sum-free subsets of abelian groups
- A quantum algorithm for approximating the influences of Boolean functions and its applications
- Hypercontractivity for global functions and sharp thresholds
- Influence and sharp-threshold theorems for monotonic measures
- On the structure of subsets of the discrete cube with small edge boundary
- The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
- A stability result for the cube edge isoperimetric inequality
- Critical window of the symmetric perceptron
- Around two theorems and a lemma by Lucio Russo
- The influence of variables in product spaces
- Towards a proof of the Fourier-entropy conjecture?
- Supercritical percolation on finite transitive graphs I: uniqueness of the giant component
- On the influences of variables on Boolean functions in product spaces
- On perfectly friendly bisections of random graphs
- Hypergraph removal lemmas via robust sharp threshold theorems
- Searching for (sharp) thresholds in random structures: where are we now?
- Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome?
- Thresholds and expectation-thresholds of monotone properties with small minterms
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Sharp thresholds for monotone non-Boolean functions and social choice theory
- Quantitative relation between noise sensitivity and influences
- Title not available (Why is that?)
- On a biased edge isoperimetric inequality for the discrete cube
- Sharp threshold for the Ising perceptron model
This page was built for publication: A structure theorem for Boolean functions with small total influences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q447936)
