Search Problems in the Decision Tree Model

DOI10.1137/S0895480192233867MaRDI QIDQ4764348zbMATH OpenFDO

Authors Moni Naor, Ilan Newman, A. Wigderson, László Lovász

Publication date 6 August 1995

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Boolean decision tree model

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Information theory (general) (94A15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• The Complexity of Decision Versus Search
• scientific article; zbMATH DE number 426344
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• Decision trees with Boolean threshold queries

Cited in

(17)

• Resolution over linear equations modulo two
• The depth of resolution proofs
• On Tseitin formulas, read-once branching programs and treewidth
• The journey from NP to TFNP hardness
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• The Complexity of Decision Versus Search
• Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
• Monotone circuit lower bounds from resolution
• Characterizing Tseitin-formulas with short regular resolution refutations
• On the complexity of finding a local maximum of functions on discrete planar subsets
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• A resolution-based interactive proof system for UNSAT
• Present and Future of Practical SAT Solving
• Extension complexity of independent set polytopes
• Communication lower bounds via critical block sensitivity
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs

This page was built for publication: Search Problems in the Decision Tree Model

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