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

DOI10.1007/s00037-011-0012-6zbMath1230.68169OpenAlexW4254122410MaRDI 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 noisemachine learningpolynomial threshold functions

Mathematics Subject Classification ID

Characteristic functions; other transforms (60E10) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (6)

Gaussian noise sensitivity and Fourier tails ⋮ Entropy in mean curvature flow ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ 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

This page was built for publication: The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions