Near-Optimal time-Space Tradeoff for Element Distinctness
Report ID: TR-139-88Author: Yao, Andrew
Date: 1988-03-00
Pages: 13
Download Formats: |PDF|
Abstract:
It was conjectured Borodin et al. (J. Comput. System Sci. 22, 1981, 351{64) that to solve the element distinctness problem requires TS = omega(n2) on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since TS = O(n2 log n) is achievable. Recently, Borodin et. al. (SIAM J. on Comput. 16, 1987, 97{9) showed that TS = omega(n3/2(log n)1/2). In this paper, we show a near-optimal tradeoff TS = omega(n2-epsilon(n)) where epsilon(n) = O(1/(log n)1/2).