On the computational power of Boolean decision lists

DOI10.1007/3-540-45841-7_30MaRDI QIDQ4736855zbMATH OpenFDO

Authors Matthias Krause

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2285/22850372.htm

zbMATH Keywords

Boolean Complexity TheoryLearnabilityLower Bounds

Mathematics Subject Classification ID

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

Recommendations

• On the computational power of Boolean decision lists
• Decision lists and related classes of Boolean functions
• Lower bounds on learning decision lists and trees
• Monotone term decision lists
• Lower bounds on learning decision lists and trees

Cited in

(7)

• On data classification by iterative linear partitioning
• Decision lists and related classes of Boolean functions
• Linear decision lists and partitioning algorithms for the construction of neural networks
• Decision List Compression by Mild Random Restrictions
• No Efficient Disjunction or Conjunction of Switch-Lists
• Decision lists and related Boolean functions
• On the computational power of Boolean decision lists

This page was built for publication: On the computational power of Boolean decision lists

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4736855)