Approximating the Noise Sensitivity of a Monotone Boolean Function
From MaRDI portal
Publication:5875511
DOI10.4230/LIPIcs.APPROX-RANDOM.2019.52OpenAlexW2978755515MaRDI QIDQ5875511
Ronitt Rubinfeld, Arsen Vasilyan
Publication date: 3 February 2023
Full work available at URL: https://arxiv.org/abs/1904.06745
Cites Work
- Unnamed Item
- Unnamed Item
- Learning intersections and thresholds of halfspaces
- The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions
- How much are increasing sets positively correlated?
- Polynomial regression under arbitrary product distributions
- Noise stability of weighted majority
- Quantitative relation between noise sensitivity and influences
- An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
- Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity
- Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
- Agnostically Learning Halfspaces
- On the noise sensitivity of monotone functions
- Analysis of Boolean Functions
- The average sensitivity of an intersection of half spaces
- Coin flipping from a cosmic source: On error correction of truly random bits
- A polynomial lower bound for testing monotonicity
- Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Hardness amplification within NP
- Noise sensitivity of Boolean functions and applications to percolation
This page was built for publication: Approximating the Noise Sensitivity of a Monotone Boolean Function
