The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions

DOI10.1007/s00037-011-0012-6zbMath1230.68169MaRDI QIDQ645127

Daniel M. Kane

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

zbMATH Keywords

Gaussian noise; machine learning; polynomial threshold functions

Mathematics Subject Classification ID

60E10: Characteristic functions; other transforms

68T05: Learning and adaptive systems in artificial intelligence

Related Items

Approximating the Noise Sensitivity of a Monotone Boolean Function, 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