Lower bounds for agnostic learning via approximate rank

DOI10.1007/s00037-010-0296-yzbMath1234.68169OpenAlexW2077497438MaRDI QIDQ626689

Adam R. Klivans, Alexander A. Sherstov

Publication date: 18 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-010-0296-y

zbMATH Keywords

lower boundcommunication complexityagnostic learningmatrix analysisapproximate rankconcept class

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Kolmogorov width and approximate rank ⋮ Polynomial approximation on disjoint segments and amplification of approximation ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities

This page was built for publication: Lower bounds for agnostic learning via approximate rank