The hardness of the expected decision depth problem

DOI10.1016/J.IPL.2006.08.012MaRDI QIDQ845910zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexitydecision trees

Mathematics Subject Classification ID

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

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

Cites work

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

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)