A structure theorem for Boolean functions with small total influences
From MaRDI portal
Publication:447936
DOI10.4007/annals.2012.176.1.9zbMath1253.05128arXiv1008.1021MaRDI QIDQ447936
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
Related Items
On the structure of subsets of the discrete cube with small edge boundary, Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems, The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups, On the failure of concentration for the \(\ell_\infty\)-ball, Noise-stability and central limit theorems for effective resistance of random electric networks, Thresholds and expectation-thresholds of monotone properties with small minterms, Boolean functions: influence, threshold and noise, Around two theorems and a lemma by Lucio Russo, A stability result for the cube edge isoperimetric inequality, On a biased edge isoperimetric inequality for the discrete cube, Random sum-free subsets of abelian groups, Towards a proof of the Fourier-entropy conjecture?, A quantum algorithm for approximating the influences of Boolean functions and its applications, Unnamed Item
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
