A Time-Space Tradeoff for Element Distinctness
From MaRDI portal
Publication:3776617
DOI10.1137/0216007zbMath0636.68040MaRDI QIDQ3776617
Avi Wigderson, Friedhelm Meyer auf der Heide, Allan Borodin, Eli Upfal, Faith E. Fich
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216007
computational complexity; sorting; space lower bounds; time-space tradeoffs; time lower bounds; element distinctness
Related Items
Time-space tradeoffs for algebraic problems on general sequential machines, Trade-offs between communication and space, Time-space tradeoffs for set operations, Alphabet dependence in parameterized matching, Time-space tradeoffs for branching programs, Determinism versus nondeterminism for linear time RAMs with memory restrictions, Time-space tradeoffs in algebraic complexity theory