Decision tree approximations of Boolean functions

DOI10.1016/S0304-3975(01)00011-1MaRDI QIDQ5958322zbMATH OpenWikidataFDO

Authors Dinesh Mehta, Vijay Raghavan

Publication date 3 March 2002

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

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00011-1

zbMATH Keywords

Boolean functions

Mathematics Subject Classification ID

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

Recommendations

• Learning decision trees from random examples
• Learning Decision Trees Using the Fourier Spectrum
• Learning Monotone Decision Trees in Polynomial Time
• Lower bounds on learning decision lists and trees
• Exact learning Boolean functions via the monotone theory

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1306863 (Why is no real title available?)
• Constructing optimal binary decision trees is NP-complete
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• Exact learning Boolean functions via the monotone theory
• Exact learning when irrelevant variables abound
• Finding small equivalent decision trees is hard
• Learning decision trees from random examples
• Occam's razor
• On boolean decision trees with faulty nodes
• Partial Occam's Razor and its applications

Cited in

(8)

• On boolean decision trees with faulty nodes
• On the complexity of problems on simple games
• scientific article; zbMATH DE number 6351494 (Why is no real title available?)
• Improved time complexities for learning Boolean networks
• Learning decision trees from random examples
• Learning stochastic decision trees
• Algorithmic Learning Theory
• Properly learning decision trees in almost polynomial time

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

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