Time-space trade-off lower bounds for randomized computation of decision problems
From MaRDI portal
Publication:3455560
DOI10.1145/636865.636867zbMath1326.68144OpenAlexW1975124543MaRDI QIDQ3455560
Erik Vee, Xiaodong Sun, P. W. Beame, Michael E. Saks
Publication date: 7 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/636865.636867
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (17)
On multi-partition communication complexity ⋮ Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice ⋮ Expanders and time-restricted branching programs ⋮ A note on the decoding complexity of error-correcting codes ⋮ Limitations of incremental dynamic programming ⋮ Element distinctness revisited ⋮ A nondeterministic space-time tradeoff for linear codes ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ Choice-memory tradeoff in allocations ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ Unnamed Item ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Typically-correct derandomization for small time and space ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism
This page was built for publication: Time-space trade-off lower bounds for randomized computation of decision problems
