Two time-space tradeoffs for element distinctness
From MaRDI portal
Publication:1095660
DOI10.1016/0304-3975(86)90150-7zbMATH Open0632.68044OpenAlexW2003223355MaRDI QIDQ1095660FDOQ1095660
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
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
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Some Monotonicity Properties of Partial Orders
- On the time-space tradeoff for sorting with linear queries
- A time-space tradeoff for language recognition
- A time-space tradeoff for sorting on non-oblivious machines
- Title not available (Why is that?)
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
- Title not available (Why is that?)
- A Time-Space Tradeoff for Element Distinctness
- The decision-tree complexity of element distinctness
- Near-Optimal Time-Space Tradeoff for Element Distinctness
- Time-space tradeoffs for SAT on nonuniform machines
- Computing (and Life) Is All about Tradeoffs
- 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)
