Near-Optimal Time-Space Tradeoff for Element Distinctness

DOI10.1137/S0097539788148959zbMath0820.68057OpenAlexW2149512830MaRDI QIDQ4312417

Andrew Chi-Chih Yao

Publication date: 27 August 1995

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539788148959

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ Time-space tradeoffs for satisfiability ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Lower bounds on the complexity of recognizing SAT by Turing machines ⋮ Determinism versus nondeterminism for linear time RAMs with memory restrictions