Determinism versus non-determinism for linear time RAMs (extended abstract)
From MaRDI portal
Publication:2819593
DOI10.1145/301250.301424zbMath1346.68093OpenAlexW2013539671MaRDI QIDQ2819593
Publication date: 29 September 2016
Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/301250.301424
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Tighter lower bounds for nearest neighbor search and related problems in the cell probe model ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs ⋮ Time-space tradeoffs for branching programs
This page was built for publication: Determinism versus non-determinism for linear time RAMs (extended abstract)
