Near-optimal time-space tradeoff for element distinctness
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
It was conjectured by A. Borodin et al. that to solve the element distinctness problem requires TS= Omega (n/sup 2/) on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since TS=O(n/sup 2/ log n) is achievable. They showed recently (1987) that TS= Omega (n/sup 3/2/(log n)/sup 1/2/). The author shows a near-optimal tradeoff TS= Omega (n/sup 2- epsilon (n)/), where epsilon (n)=O(1/(log n)/sup 1/2/).Keywords
This publication has 11 references indexed in Scilit:
- Nondeterministic linear tasks may require substantially nonlinear deterministic time in the case of sublinear work spacePublished by Association for Computing Machinery (ACM) ,1988
- A Time-Space Tradeoff for Element DistinctnessSIAM Journal on Computing, 1987
- A simple proof of a time-space trade-off for sorting with linear comparisonsTheoretical Computer Science, 1986
- Two time-space tradeoffs for element distinctnessTheoretical Computer Science, 1986
- A time-space tradeoff for language recognitionTheory of Computing Systems, 1984
- On the time-space tradeoff for sorting with linear queriesTheoretical Computer Science, 1982
- A time-space tradeoff for sorting on non-oblivious machinesJournal of Computer and System Sciences, 1981
- Time-space tradeoffs for computing functions, using connectivity properties of their circuitsJournal of Computer and System Sciences, 1980
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979
- The recognition problem for the set of perfect squaresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1966