A Time-Space Tradeoff for Element Distinctness

DOI10.1137/0216007MaRDI QIDQ3776617zbMATH OpenOpenAlexFDO

Authors Allan Borodin, Friedhelm Meyer auf der Heide, Eli Upfal, A. Wigderson, 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

zbMATH Keywords

computational complexityelement distinctnesssortingspace lower boundstime lower boundstime-space tradeoffs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3980480
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• Element Distinctness and Sorting on One-Tape Off-Line Turing Machines
• Two time-space tradeoffs for element distinctness
• A general Sequential Time-Space Tradeoff for Finding Unique Elements

Cited in

(16)

• A simple proof of a time-space trade-off for sorting with linear comparisons
• Two time-space tradeoffs for element distinctness
• 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
• Computing (and Life) Is All about Tradeoffs
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• scientific article; zbMATH DE number 3980480 (Why is no real title available?)
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• scientific article; zbMATH DE number 2119639 (Why is no real title available?)
• Quantum time-space tradeoff for finding multiple collision pairs
• On the time-space tradeoff for sorting with linear queries

This page was built for publication: A Time-Space Tradeoff for Element Distinctness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3776617)