Two time-space tradeoffs for element distinctness
type: Item
instance of: scholarly article
title: Two time-space tradeoffs for element distinctness
zbMATH Open document ID: 0632.68044
DOI: 10.1016/0304-3975(86)90150-7
author: Mauricio Karchmer
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: Two time-space tradeoffs for element distinctness are given. The first one shows \(T^ 2S=\Omega (n^ 3)\) on a branching program using minimum operations. By a result of \textit{A. C. C. Yao} [ibid. 19, 203-218 (1982; Zbl 0547.68062)], this implies the same bounds for linear queries. The second result extends one by \textit{P. Dúriś} and \textit{Z. Galil} [Math. Syst. Theory 17, 3-12 (1984; Zbl 0533.68047)] who constructed a Boolean function that requires \(T^ 2S=\Omega (n^ 3)\) on a k-headed Turing machine. Here it is shown that their proof also holds for element distinctness, a more natural problem.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4028900
zbMATH Keywords: element distinctness
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90150-7
OpenAlex ID: W2003223355
cites work: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
cites work: Q3745272
cites work: A time-space tradeoff for sorting on non-oblivious machines
cites work: A time-space tradeoff for language recognition
cites work: Some Monotonicity Properties of Partial Orders
cites work: Time-space tradeoffs for computing functions, using connectivity properties of their circuits
cites work: On the time-space tradeoff for sorting with linear queries
Recommended article: A Time-Space Tradeoff for Element Distinctness
Recommended article: Q3745272
Recommended article: Near-Optimal Time-Space Tradeoff for Element Distinctness
Recommended article: A general Sequential Time-Space Tradeoff for Finding Unique Elements
Recommended article: Q4601908
Recommended article: Size-treewidth tradeoffs for circuits computing the element distinctness function
Recommended article: Space-Time Trade-Offs for the Shortest Unique Substring Problem.
Recommended article: Space-time trade-offs for finding shortest unique substrings and maximal unique matches
Recommended article: On the optimal time/space tradeoff for hash tables
Recommended article: Time-space trade-offs for longest common extensions
description: scientific article; zbMATH DE number 4028900