Bounding the sensitivity of polynomial threshold functions

DOI10.4086/TOC.2014.V010A001MaRDI QIDQ3191612zbMATH OpenOpenAlexFDO

Authors Prahladh Harsha, Adam R. Klivans, Raghu Meka

Publication date 6 October 2014

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2014.v010a001

zbMATH Keywords

average sensitivitypolynomial threshold function

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32)

Recommendations

• Average sensitivity and noise sensitivity of polynomial threshold functions
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
• The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions
• A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions
• The correct exponent for the Gotsman-Linial conjecture

Cites work

• Noise sensitivity and chaos in social choice theory
• The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions

Cited in

(17)

• Polynomial regression under arbitrary product distributions
• A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions
• Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems
• A comparison study of two modified analytical approach for the solution of nonlinear fractional shallow water equations in fluid flow
• Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
• Upper bounds on Fourier entropy
• Upper bounds on Fourier entropy
• The average sensitivity of an intersection of half spaces
• Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
• The correct exponent for the Gotsman-Linial conjecture
• The average sensitivity of an intersection of half spaces
• An invariance principle for polytopes
• Average sensitivity and noise sensitivity of polynomial threshold functions
• Concentration and moment inequalities for polynomials of independent random variables
• New degree bounds for polynomial threshold functions
• The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions

This page was built for publication: Bounding the sensitivity of polynomial threshold functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191612)