Decision trees with Boolean threshold queries

DOI10.1006/JCSS.1995.1085MaRDI QIDQ1908341zbMATHOpenAlexFDO

Authors Yosi Ben-Asher, Ilan Newman

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

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)

Recommendations

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

Cited in

(17)

• On the decision tree complexity of threshold functions
• Lower bounds for linear decision trees with bounded weights
• Applications of Ramsey's theorem to decision tree complexity
• Randomized versus deterministic decision tree size
• On the Decision Tree Complexity of Threshold Functions
• Optimal direct sum results for deterministic and randomized decision tree complexity
• On the power of parity queries in Boolean decision trees
• Geometric approach for optimal routing on a mesh with buses
• scientific article; zbMATH DE number 176776 (Why is no real title available?)
• Lower bounds for linear decision trees via an energy complexity argument
• Secure and highly-available aggregation queries in large-scale sensor networks via set sampling
• Optimal separation and strong direct sum for randomized query complexity
• Power of decision trees with monotone queries
• scientific article; zbMATH DE number 426344 (Why is no real title available?)
• On boolean decision trees with faulty nodes
• scientific article; zbMATH DE number 3854414 (Why is no real title available?)
• On (simple) decision tree rank

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)