A structure theorem for Boolean functions with small total influences
From MaRDI portal
Publication:447936
DOI10.4007/annals.2012.176.1.9zbMath1253.05128arXiv1008.1021OpenAlexW2963226739MaRDI 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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
