Search Problems in the Decision Tree Model
From MaRDI portal
Publication:4764348
DOI10.1137/S0895480192233867zbMATH Open0817.68112MaRDI QIDQ4764348FDOQ4764348
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)
Recommendations
Combinatorics in computer science (68R05) Information theory (general) (94A15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Cited In (17)
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- 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
- Characterizing Tseitin-formulas with short regular resolution refutations
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- The Complexity of Decision Versus Search
- On Tseitin formulas, read-once branching programs and treewidth
- Monotone circuit lower bounds from resolution
- The journey from NP to TFNP hardness
- Resolution over linear equations modulo two
- The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
- A resolution-based interactive proof system for UNSAT
- Extension complexity of independent set polytopes
- The depth of resolution proofs
- Present and Future of Practical SAT Solving
- 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)
