New degree bounds for polynomial threshold functions
From MaRDI portal
Publication:5901091
DOI10.1145/780542.780592zbMath1192.94146OpenAlexW2038111284MaRDI QIDQ5901091
Ryan O'Donnell, Rocco A. Servedio
Publication date: 16 August 2010
Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/780542.780592
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (9)
On PAC learning algorithms for rich Boolean function classes ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ Polynomial regression under arbitrary product distributions ⋮ New degree bounds for polynomial threshold functions ⋮ Learning intersections of halfspaces with a margin ⋮ Extremal properties of polynomial threshold functions ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ Unconditional lower bounds for learning intersections of halfspaces
This page was built for publication: New degree bounds for polynomial threshold functions
