The hardness of the expected decision depth problem

DOI10.1016/J.IPL.2006.08.012zbMATH Open1185.68653OpenAlexW1966141525MaRDI QIDQ845910FDOQ845910

Authors: Dana Ron, Amir Rosenfeld, Salil Vadhan 

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.08.012

Recommendations

• Decision-theoretic troubleshooting: hardness of approximation
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• A decision-theoretic extension of stochastic complexity and its applications to learning
• On stochastic complexity estimation: a decision-theoretic approach
• scientific article; zbMATH DE number 17813
• Publication:4892375
• On the hardness of the minimum height decision tree problem
• Complexity of extremal set decision problem
• On the decision tree depth
• scientific article; zbMATH DE number 1098497

zbMATH Keywords

computational complexitydecision trees

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Learning with attribute costs
• Query strategies for priced information
• A new strategy for querying priced information
• Optimal Information Gathering on the Internet with Time and Cost Constraints

Cited In (3)

• The computational complexity of understanding binary classifier decisions
• Information Acquisition Under Resource Limitations in a Noisy Environment
• Depth of Reasoning and Information Revelation: An Experiment on the Distribution of k-Levels

This page was built for publication: The hardness of the expected decision depth problem

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