The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions
From MaRDI portal
Publication:645127
DOI10.1007/s00037-011-0012-6zbMath1230.68169MaRDI QIDQ645127
Publication date: 8 November 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0012-6
60E10: Characteristic functions; other transforms
68T05: Learning and adaptive systems in artificial intelligence
Related Items
Approximating the Noise Sensitivity of a Monotone Boolean Function, Entropy in mean curvature flow, Gaussian noise sensitivity and Fourier tails, Noise stability and correlation with half spaces, Robust optimality of Gaussian noise stability, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
- Noise stability of functions with low influences: invariance and optimality
- Spectral properties of threshold functions
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Hardness amplification within NP