Decision tree approximations of Boolean functions

DOI10.1016/S0304-3975(01)00011-1zbMath0988.68136WikidataQ56340226 ScholiaQ56340226MaRDI QIDQ5958322

Dinesh P. Mehta, Vijay Raghavan

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

Improved time complexities for learning Boolean networks ⋮ On the complexity of problems on simple games

Cites Work

• Unnamed Item
• Unnamed Item
• Occam's razor
• Partial Occam's Razor and its applications
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• Constructing optimal binary decision trees is NP-complete
• Exact learning when irrelevant variables abound
• Learning decision trees from random examples
• Exact learning Boolean functions via the monotone theory
• On boolean decision trees with faulty nodes
• FINDING SMALL EQUIVALENT DECISION TREES IS HARD

This page was built for publication: Decision tree approximations of Boolean functions