Lower bounds on learning decision lists and trees

DOI10.1007/3-540-59042-0_102zbMath1379.68271OpenAlexW2187284394MaRDI QIDQ4596650

Tao Jiang, Thomas R. Hancock, John Tromp, Ming Li

Publication date: 4 December 2017

Published in: STACS 95 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59042-0_102

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (3)

Partial Occam's Razor and its applications ⋮ The complexity of properly learning simple concept classes ⋮ On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.

This page was built for publication: Lower bounds on learning decision lists and trees