Time-space tradeoffs for set operations (Q1210542): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Time-Space Tradeoff for Element Distinctness / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A time-space tradeoff for sorting on non-oblivious machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two time-space tradeoffs for element distinctness / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the time-space tradeoff for sorting with linear queries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer / rank | |||
Normal rank |
Latest revision as of 16:59, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Time-space tradeoffs for set operations |
scientific article |
Statements
Time-space tradeoffs for set operations (English)
0 references
30 August 1993
0 references
The paper deals with \(R\)-way branching programs as well as with a more restricted model of comparison branching programs. The authors show the time-space tradeoff \(TS=\Omega(n^ 2)\) for the set complementation and \(TS-\Omega(n^{3/2})\) for the set intersection problem. Tradeoffs of such type were known before. The authors extend them for other problems including the set union, set disjointedness and set intersection problems. The lower bound argument is standard: show that for a random instances any small decision tree produces only few distinct outputs while the problem itself has many outputs. The main difficulties appear when estimating these probabilities for concrete problems.
0 references
branching programs
0 references
time-space tradeoff
0 references
lower bound
0 references