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)

Full work available at URL https://doi.org/10.1137/S0895480192233867

zbMATH Keywords

Boolean decision tree model

Mathematics Subject Classification ID

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

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

(23)

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

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)