New degree bounds for polynomial threshold functions
From MaRDI portal
Publication:5901091
DOI10.1145/780542.780592zbMath1192.94146MaRDI 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
68Q32: Computational learning theory
68T05: Learning and adaptive systems in artificial intelligence
Related Items
Unnamed Item, New degree bounds for polynomial threshold functions, Optimal bounds for sign-representing the intersection of two halfspaces by polynomials, A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length, Unconditional lower bounds for learning intersections of halfspaces, Polynomial regression under arbitrary product distributions, On PAC learning algorithms for rich Boolean function classes, Learning intersections of halfspaces with a margin, Extremal properties of polynomial threshold functions