A general Sequential Time-Space Tradeoff for Finding Unique Elements

DOI10.1137/0220017zbMATH Open0722.68062OpenAlexW2056431243MaRDI QIDQ3210181FDOQ3210181

Authors: Paul Beame 

Publication date: 1991

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

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

Recommendations

• A Time-Space Tradeoff for Element Distinctness
• scientific article; zbMATH DE number 3980480
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• Two time-space tradeoffs for element distinctness
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Space-time trade-offs for the shortest unique substring problem
• scientific article; zbMATH DE number 2087050
• Deterministic time-space trade-offs for \(k\)-SUM
• Upper bounds for time-space trade-offs in sorting and selection
• On the space complexity of some algorithms for sequence comparison

zbMATH Keywords

computational complexitylower boundsortingbranching programtime-space tradeoff

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cited In (31)

• Finding the Median (Obliviously) with Bounded Space
• Approximation in (Poly-) logarithmic space
• Strictly in-place algorithms for permuting and inverting permutations
• Two time-space tradeoffs for element distinctness
• Graph properties checkable in linear time in the number of vertices
• A Survey on Priority Queues
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Frameworks for designing in-place graph algorithms
• Priority Queues and Sorting for Read-Only Data
• Finding median in read-only memory on integer input
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Title not available (Why is that?)
• Runtime analysis of the \((1+1)\) EA on computing unique input output sequences
• Approximation in (Poly-) Logarithmic Space
• Tight time-space lower bounds for finding multiple collision pairs and their applications
• A Time-Space Tradeoff for Element Distinctness
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• On lower bounds for read-\(k\)-times branching programs
• Choice-memory tradeoff in allocations
• Time-space tradeoffs for branching programs
• Time-space tradeoffs for SAT on nonuniform machines
• Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays.
• On the time-space tradeoff for sorting with linear queries
• Title not available (Why is that?)
• Time-space tradeoffs for set operations
• Space-efficient biconnected components and recognition of outerplanar graphs
• Selection from read-only memory with limited workspace
• Time-space tradeoffs in algebraic complexity theory
• A simple proof of a time-space trade-off for sorting with linear comparisons
• A Framework for In-place Graph Algorithms

This page was built for publication: A general Sequential Time-Space Tradeoff for Finding Unique Elements

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