Decision Trees and Influences of Variables Over Product Probability Spaces
From MaRDI portal
Publication:3557496
DOI10.1017/S0963548309009833zbMath1193.60007arXivmath/0612405OpenAlexW2069653438MaRDI QIDQ3557496
Publication date: 23 April 2010
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0612405
Combinatorial probability (60C05) Probabilistic measure theory (60A10) General harmonic expansions, frames (42C15)
Related Items
On the failure of concentration for the \(\ell_\infty\)-ball, Extended commonality of paths and cycles via Schur convexity, Geometric influences, A structure theorem for Boolean functions with small total influences, A simple reduction from a biased measure on the discrete cube to the uniform measure, Geometric influences. II: Correlation inequalities and noise sensitivity, Unnamed Item, Influence in product spaces, On the Influences of Variables on Boolean Functions in Product Spaces, Juntas in theℓ1-grid and Lipschitz maps between discrete tori, Lower bound on the correlation between monotone families in the average case
Cites Work
- Isoperimetry and integrability of the sum of independent Banach-space valued random variables
- Inequalities in Fourier analysis
- Boolean functions with low average sensitivity depend on few coordinates
- On Russo's approximate zero-one law
- The influence of variables in product spaces
- On the distribution of the Fourier spectrum of Boolean functions
- Boolean functions whose Fourier transform is concentrated on the first two levels.
- The hardness of 3-uniform hypergraph coloring
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Constant depth circuits, Fourier transform, and learnability
- Learning Monotone Decision Trees in Polynomial Time
- On the critical percolation probabilities
- Sharp thresholds of graph properties, and the $k$-sat problem
- Every monotone graph property has a sharp threshold
- Influences in Product Spaces: KKL and BKKKL Revisited
