Decision trees: Old and new results.

DOI10.1006/inco.1999.2788zbMath1045.68983OpenAlexW2093331391MaRDI QIDQ1854291

Rudolf Fleischer

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1999.2788

zbMATH Keywords

mlf-functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimale Erzeugung von Positivbereichen
• Lower bounds on probabilistic linear decision trees
• Obtaining lower bounds using artificial components
• Minimal generation of basic open semianalytic sets
• A tight lower bound for the complexity of path-planning for a disc
• On selecting the k largest with median tests
• Comparisons between linear functions can help
• On selecting the \(k\) largest with restricted quadratic queries
• On the complexity of computations under varying sets of primitives
• A note on Rabin's width of a complete proof
• Simulating probabilistic by deterministic algebraic computation trees
• Proving simultaneous positivity of linear forms
• The Computational Complexity of Continued Fractions
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• Applications of Ramsey's theorem to decision tree complexity
• On the Polyhedral Decision Problem
• Lower bounds for algebraic decision trees
• A Counting Approach to Lower Bounds for Selection Problems
• Rabin's width of a complete proof and the width of a semialgebraic set
• On the Optimality of Some Set Algorithms

This page was built for publication: Decision trees: Old and new results.