scientific article; zbMATH DE number 1256781

MaRDI QIDQ4228517zbMATH OpenFDO

Authors Friedhelm Meyer auf der Heide, Roman Smolensky, Dima Grigoriev, Marek Karpinski

Publication date 4 October 1999

zbMATH Keywords

knapsack problem

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A lower bound for randomized algebraic decision trees
• Lower bounds for external algebraic decision trees
• scientific article; zbMATH DE number 19781
• An exponential lower bound on the size of algebraic decision trees for MAX
• An improved lower bound for the randomized decision tree complexity of recursive majority
• Randomization and the computational power of analytic and algebraic decision trees
• Lower bounds on probabilistic linear decision trees
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• Improved bounds for the randomized decision tree complexity of recursive majority
• Optimal direct sum results for deterministic and randomized decision tree complexity

Cited in

(9)

• Lower bounds on probabilistic linear decision trees
• On randomized semi-algebraic test complexity
• Nearly sharp complexity bounds for multiprocessor algebraic computations
• A lower bound for randomized algebraic decision trees
• Randomization and the computational power of analytic and algebraic decision trees
• Decision trees: Old and new results.
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• scientific article; zbMATH DE number 1559524 (Why is no real title available?)
• scientific article; zbMATH DE number 1390051 (Why is no real title available?)

This page was built for publication:

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