Search Problems in the Decision Tree Model

DOI10.1137/S0895480192233867zbMath0817.68112MaRDI QIDQ4764348

Ilan Newman, László Lovász, Avi Wigderson, Moni Naor

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) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Information theory (general) (94A15)

Related Items

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, On the complexity of finding a local maximum of functions on discrete planar subsets, The Journey from NP to TFNP Hardness, Communication Lower Bounds via Critical Block Sensitivity, Extension Complexity of Independent Set Polytopes, Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds, The depth of resolution proofs, 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, Unnamed Item, Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs., Present and Future of Practical SAT Solving, Resolution over linear equations modulo two, Characterizing Tseitin-formulas with short regular resolution refutations