A general Sequential Time-Space Tradeoff for Finding Unique Elements
From MaRDI portal
Publication:3210181
DOI10.1137/0220017zbMath0722.68062OpenAlexW2056431243MaRDI QIDQ3210181
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
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Related Items (22)
On lower bounds for read-\(k\)-times branching programs ⋮ Strictly in-place algorithms for permuting and inverting permutations ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Graph properties checkable in linear time in the number of vertices ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Space-efficient biconnected components and recognition of outerplanar graphs ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Priority Queues and Sorting for Read-Only Data ⋮ Choice-memory tradeoff in allocations ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ Approximation in (Poly-) logarithmic space ⋮ Selection from read-only memory with limited workspace ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ A Survey on Priority Queues ⋮ Finding median in read-only memory on integer input ⋮ Time-space tradeoffs for branching programs ⋮ Determinism versus nondeterminism for linear time RAMs with memory restrictions
This page was built for publication: A general Sequential Time-Space Tradeoff for Finding Unique Elements
