A general Sequential Time-Space Tradeoff for Finding Unique Elements
type: Item
instance of: scholarly article
title: A general Sequential Time-Space Tradeoff for Finding Unique Elements
zbMATH Open document ID: 0722.68062
DOI: 10.1137/0220017
published in: SIAM Journal on Computing
publication date: 1991-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 4191123
zbMATH Keywords: time-space tradeoff
zbMATH Keywords: computational complexity
zbMATH Keywords: lower bound
zbMATH Keywords: sorting
zbMATH Keywords: branching program
author: Paul Beame
MaRDI profile type: MaRDI publication profile
full work available at URL: https://doi.org/10.1137/0220017
OpenAlex ID: W2056431243
Recommended article: A Time-Space Tradeoff for Element Distinctness
Recommended article: Q3745272
Recommended article: Near-Optimal Time-Space Tradeoff for Element Distinctness
Recommended article: Two time-space tradeoffs for element distinctness
Recommended article: Space-time trade-offs for finding shortest unique substrings and maximal unique matches
Recommended article: Space-Time Trade-Offs for the Shortest Unique Substring Problem.
Recommended article: Q4737696
Recommended article: Q4598197
Recommended article: Upper bounds for time-space trade-offs in sorting and selection
Recommended article: On the space complexity of some algorithms for sequence comparison
description: scientific article; zbMATH DE number 4191123