Decision trees with Boolean threshold queries

DOI10.1006/JCSS.1995.1085zbMATH Open0839.68075OpenAlexW2006573851MaRDI QIDQ1908341FDOQ1908341

Ilan Newman, Yosi Ben-Asher

Publication date: 19 March 1996

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1085

Recommendations

• Bounds on the depth of decision trees that compute Boolean functions
• scientific article; zbMATH DE number 426344
• scientific article
• Lower bounds for linear decision trees via an energy complexity argument
• scientific article; zbMATH DE number 741345

zbMATH Keywords

decision trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (14)

• Applications of Ramsey's theorem to decision tree complexity
• On boolean decision trees with faulty nodes
• Title not available (Why is that?)
• Optimal direct sum results for deterministic and randomized decision tree complexity
• Power of decision trees with monotone queries
• On (simple) decision tree rank
• Title not available (Why is that?)
• On the Decision Tree Complexity of Threshold Functions
• Randomized versus deterministic decision tree size
• Title not available (Why is that?)
• Geometric approach for optimal routing on a mesh with buses
• Secure and highly-available aggregation queries in large-scale sensor networks via set sampling
• Title not available (Why is that?)
• On the decision tree complexity of threshold functions

This page was built for publication: Decision trees with Boolean threshold queries

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