Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets

DOI10.1137/050647517zbMath1147.68026OpenAlexW2065429151MaRDI QIDQ5432367

John M. Hitchcock

Publication date: 3 January 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050647517

zbMATH Keywords

computational complexitysparse setspolynomial-time reductionsresource-bounded measureresource-bounded dimension

Mathematics Subject Classification ID

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

Related Items (4)

Dimension, halfspaces, and the density of hard sets ⋮ Pushdown dimension ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds

This page was built for publication: Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets