On the noise sensitivity of monotone functions

DOI10.1002/rsa.10097zbMath1047.68106OpenAlexW2079520411MaRDI QIDQ4431436

Elchanan Mossel, Ryan O'Donnell

Publication date: 22 October 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10097

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Boolean functions (06E30)

Related Items

Learning juntas in the presence of noise, Probabilistic view of voting, paradoxes, and manipulation, On the nonlinearity of monotone Boolean functions, Learning random monotone DNF, Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome?, A stronger LP bound for formula size lower bounds via clique constraints, Exclusion sensitivity of Boolean functions, Quantitative relation between noise sensitivity and influences, Approximating the Noise Sensitivity of a Monotone Boolean Function, Annihilation and coalescence on binary trees, Computing majority by constant depth majority circuits with low fan-in gates, A Polynomial Lower Bound for Testing Monotonicity

Cites Work

• Hardness amplification within NP