A general Sequential Time-Space Tradeoff for Finding Unique Elements

DOI10.1137/0220017MaRDI QIDQ3210181zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

branching programcomputational complexitylower boundsortingtime-space tradeoff

Mathematics Subject Classification ID

Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) 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
• 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

Cited in

(37)

• 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 set operations
• Time-space tradeoffs for branching programs
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• Time-space tradeoffs in algebraic complexity theory
• Approximation in (poly-) logarithmic space
• Tight time-space lower bounds for finding multiple collision pairs and their applications
• Frameworks for designing in-place graph algorithms
• Finding median in read-only memory on integer input
• On lower bounds for read-\(k\)-times branching programs
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• A survey on priority queues
• Finding the Median (Obliviously) with Bounded Space
• scientific article; zbMATH DE number 3980480 (Why is no real title available?)
• A Time-Space Tradeoff for Element Distinctness
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• scientific article; zbMATH DE number 2119639 (Why is no real title available?)
• Priority queues and sorting for read-only data
• Extra space during initialization of succinct data structures and dynamical initializable arrays
• A framework for in-place graph algorithms
• Approximation in (Poly-) Logarithmic Space
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Time-space tradeoffs for SAT on nonuniform machines
• Graph properties checkable in linear time in the number of vertices
• Space-efficient biconnected components and recognition of outerplanar graphs
• Randomized vs. deterministic separation in time-space tradeoffs of multi-output functions
• Cumulative memory lower bounds for randomized and quantum computation
• Substring complexity in sublinear space
• Sorting and ranking of self-delimiting numbers with applications to outerplanar graph isomorphism
• Quantum time-space tradeoff for finding multiple collision pairs
• Quantum time-space tradeoffs for matrix problems
• Selection from read-only memory with limited workspace
• On the time-space tradeoff for sorting with linear queries
• Strictly in-place algorithms for permuting and inverting permutations
• Runtime analysis of the (1+1) EA on computing unique input output sequences
• Choice-memory tradeoff in allocations

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)