Decision Trees and Influences of Variables Over Product Probability Spaces

DOI10.1017/S0963548309009833zbMath1193.60007arXivmath/0612405OpenAlexW2069653438MaRDI QIDQ3557496

Hamed Hatami

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

Mathematics Subject Classification ID

Combinatorial probability (60C05) Probabilistic measure theory (60A10) General harmonic expansions, frames (42C15)

Related Items (11)

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ℓ₁-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

This page was built for publication: Decision Trees and Influences of Variables Over Product Probability Spaces