On the noise sensitivity of monotone functions

No abstract is available for this paper.

• Publication year

  2003

• Venue

  Random Struct. Algorithms

• Publication date

  2003-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/rsa.10097
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Structural Complexity II

  2012cited by this paper
• I Computational Complexity

  2005cited by this paper
• Learning intersections and thresholds of halfspaces

  2002cited by this paper
• Hardness amplification within NP

  2002influential reference
• Theory of Computational Complexity

  2000cited by this paper
• Symposium on the Theory of Computation

  1999cited by this paper
• Uniform-distribution attribute noise learnability

  1999cited by this paper
• Recursive reconstruction on periodic trees

  1998cited by this paper
• Boolean Functions With Low Average Sensitivity Depend On Few Coordinates

  1998cited by this paper
• Noise sensitivity of Boolean functions and applications to percolation

  1998influential reference
• On boundaries and influences

  1997cited by this paper
• How much are increasing sets positively correlated?

  1996cited by this paper
• On the Fourier spectrum of monotone functions

  1996cited by this paper
• Every monotone graph property has a sharp threshold

  1996influential reference
• Neural networks

  1995cited by this paper
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution

  1994cited by this paper
• On Russo's Approximate Zero-One Law

  1994cited by this paper
• Learning Boolean Functions via the Fourier Transform

  1994cited by this paper
• Collective Coin Flipping

  1989cited by this paper
• Constant depth circuits, Fourier transform, and learnability

  1989cited by this paper
• The influence of variables on Boolean functions

  1988influential reference
• A theory of the learnable

  1984cited by this paper
• Families of Non-disjoint subsets*

  1966cited by this paper

• Local strategies are pretty good at computing Boolean properties of quantum sequences

  2026cites this paper
• Halfspaces are hard to test with relative error

  2025cites this paper
• Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions

  2025cites this paper
• Probabilistic view of voting, paradoxes, and manipulation

  2021cites this paper
• Quantum Random Access Codes for Boolean Functions

  2020cites this paper
• CUNY Academic Works CUNY Academic Works

  2020influential citation
• Probabilistic Aspects of Voting, Intransitivity and Manipulation

  2020cites this paper
• Approximating the noise sensitivity of a monotone Boolean function

  2019influential citation
• 52 : 2 Approximating the Noise Sensitivity of a Monotone Boolean Function Funding

  2019cites this paper
• On the nonlinearity of monotone Boolean functions

  2018cites this paper
• C C ] 3 0 O ct 2 01 4 Learning circuits with few negations

  2018cites this paper
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

  2017cites this paper
• Computing majority with low-fan-in majority queries

  2017cites this paper
• Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

  2016cites this paper
• Unconditional Lower Bounds in Complexity Theory

  2015influential citation
• Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions

  2015influential citation
• Learning Circuits with Few Negations Boolean functions are not that monoton(ous).

  2015cites this paper
• A polynomial lower bound for testing monotonicity

  2015influential citation
• Learning circuits with few negations

  2014cites this paper
• Approximate resilience, monotonicity, and the complexity of agnostic learning

  2014cites this paper
• Analytic Methods in Concrete Complexity

  2014cites this paper
• Scaling limits for the threshold window: When does a monotone Boolean function flip its outcome?

  2014cites this paper
• On canalizing Boolean functions

  2014cites this paper
• Quantitative relation between noise sensitivity and influences

  2013cites this paper
• Annihilation and coalescence on binary trees

  2013cites this paper
• Bounds on the Average Sensitivity of Nested Canalizing Functions

  2012cites this paper
• How is Voting Theory Really Useful in Multiagent Systems ?

  2012cites this paper
• Noise Sensitivity of Boolean Functions and Percolation

  2011cites this paper
• Exclusion sensitivity of Boolean functions

  2011cites this paper
• Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

  2011cites this paper
• Learning Talagrand DNF Formulas.

  2010cites this paper
• Social Choice and Networks Lecture Date : October 5 , 2010 Lecture : Errors in Binary Voting

  2010cites this paper
• Learning, cryptography, and the average case

  2010cites this paper
• Lecture: Errors in Binary Voting

  2010cites this paper
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions

  2010cites this paper
• Quantitative relation between noise sensitivity and influences

  2010cites this paper
• A stronger LP bound for formula size lower bounds via clique constraints

  2009cites this paper
• A survey on dynamical percolation

  2009cites this paper
• 2 9 Ja n 20 09 A survey of dynamical percolation

  2009cites this paper
• On the learnability of monotone functions

  2009cites this paper
• Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions

  2009cites this paper
• Optimal Cryptographic Hardness of Learning Monotone Functions

  2008cites this paper
• Learning random monotone DNF

  2008cites this paper
• Applications of unconditional pseudorandomness in complexity theory

  2007cites this paper
• Hardness Amplification for Errorless Heuristics

  2007cites this paper
• Learning concepts with few unknown relevant attributes from noisy data

  2006cites this paper
• On the Optimality of the Dimensionality Reduction Method

  2006cites this paper
• The complexity of hardness amplification and derandomization

  2006cites this paper
• Kolmogorov Complexity and formula size lower bounds

  2006cites this paper
• Learning juntas in the presence of noise

  2006cites this paper
• Average Sensitivity of Typical Monotone Boolean Functions

  2005cites this paper
• On the Lyapunov Exponent of Monotone Boolean Networks †

  2005cites this paper
• THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS

  2005cites this paper
• Noise sensitivity and chaos in social choice theory

  2005cites this paper
• Transfer theorems and asymptotic distributional results for m-ary search trees

  2005cites this paper
• On uniform amplification of hardness in NP

  2005cites this paper
• Coin flipping from a cosmic source: On error correction of truly random bits

  2004cites this paper
• Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?

  2004cites this paper
• Using nondeterminism to amplify hardness

  2004cites this paper
• Computational applications of noise sensitivity

  2003influential citation
• Hardness amplification within NP

  2002cites this paper