Near-Optimal time-Space Tradeoff for Element Distinctness

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).