A structure theorem for Boolean functions with small total influences
From MaRDI portal
(Redirected from Publication:447936)
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.
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
- scientific article; zbMATH DE number 3503316 (Why is no real title available?)
- scientific article; zbMATH DE number 1503603 (Why is no real title available?)
- A Class of Statistics with Asymptotically Normal Distribution
- An approximate zero-one law
- Boolean functions with low average sensitivity depend on few coordinates
- Decision Trees and Influences of Variables Over Product Probability Spaces
- Every monotone graph property has a sharp threshold
- Hunting for sharp thresholds
- Influences of variables and threshold intervals under group symmetries
- Noise stability of functions with low influences: invariance and optimality
- On Russo's approximate zero-one law
- On the critical percolation probabilities
- Sharp thresholds of graph properties, and the $k$-sat problem
- The influence of variables in product spaces
- The jackknife estimate of variance
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
Cited in
(29)- Supercritical percolation on finite transitive graphs I: uniqueness of the giant component
- Sharp thresholds for monotone non-Boolean functions and social choice theory
- Quantitative relation between noise sensitivity and influences
- On the influences of variables on Boolean functions in product spaces
- Thresholds and expectation-thresholds of monotone properties with small minterms
- On the failure of concentration for the \(\ell_\infty\)-ball
- The influence of variables in product spaces
- Noise-stability and central limit theorems for effective resistance of random electric networks
- Influence and sharp-threshold theorems for monotonic measures
- Searching for (sharp) thresholds in random structures: where are we now?
- On the structure of subsets of the discrete cube with small edge boundary
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Boolean functions: influence, threshold and noise
- A quantum algorithm for approximating the influences of Boolean functions and its applications
- Critical window of the symmetric perceptron
- Approximation of biased Boolean functions of small total influence by DNFs
- Around two theorems and a lemma by Lucio Russo
- The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
- scientific article; zbMATH DE number 6351493 (Why is no real title available?)
- A stability result for the cube edge isoperimetric inequality
- On a biased edge isoperimetric inequality for the discrete cube
- Hypercontractivity for global functions and sharp thresholds
- Sharp threshold for the Ising perceptron model
- Forbidden intersections for codes
- Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome?
- Towards a proof of the Fourier-entropy conjecture?
- Random sum-free subsets of abelian groups
- Hypergraph removal lemmas via robust sharp threshold theorems
- On perfectly friendly bisections of random graphs
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)
