Two time-space tradeoffs for element distinctness

DOI10.1016/0304-3975(86)90150-7MaRDI QIDQ1095660zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A Time-Space Tradeoff for Element Distinctness
• scientific article; zbMATH DE number 3980480
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• Space-time trade-offs for the shortest unique substring problem
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• On the optimal time/space tradeoff for hash tables
• Time-space trade-offs for longest common extensions

Cites work

• scientific article; zbMATH DE number 3980480 (Why is no real title available?)
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• A time-space tradeoff for language recognition
• A time-space tradeoff for sorting on non-oblivious machines
• On the time-space tradeoff for sorting with linear queries
• Some Monotonicity Properties of Partial Orders
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits

Cited in

(12)

• Lower bounds on the complexity of recognizing SAT by Turing machines
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• scientific article; zbMATH DE number 3980480 (Why is no real title available?)
• A Time-Space Tradeoff for Element Distinctness
• The decision-tree complexity of element distinctness
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• Computing (and Life) Is All about Tradeoffs
• Time-space tradeoffs for SAT on nonuniform machines
• Time-space tradeoffs for set operations
• Time-space tradeoffs for satisfiability
• A general Sequential Time-Space Tradeoff for Finding Unique Elements

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

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