Two time-space tradeoffs for element distinctness

DOI10.1016/0304-3975(86)90150-7zbMath0632.68044OpenAlexW2003223355MaRDI QIDQ1095660

Mauricio Karchmer

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90150-7

zbMATH Keywords

element distinctness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (7)

Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs ⋮ Time-space tradeoffs for set operations ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ 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

Cites Work

• Unnamed Item
• On the time-space tradeoff for sorting with linear queries
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• A time-space tradeoff for sorting on non-oblivious machines
• A time-space tradeoff for language recognition
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Some Monotonicity Properties of Partial Orders

This page was built for publication: Two time-space tradeoffs for element distinctness