A Time-Space Tradeoff for Element Distinctness

In A time space tradeoff for sorting on non-oblivious machines, Borodin et al. [J. Comput. System Sci., 22 (1981), pp. 351–364] proved that to sort n elements requires $TS = \Omega (n^2 )$ where $T = $ time and $S = $ space on a comparison based branching program. Although element distinctness and sorting are equivalent problems on a computation tree, the stated tradeoff result does not immediately follow for element distinctness or indeed for any decision problem. In this paper, we are able to show that $TS = \Omega (n^{{3 / 2}} \sqrt {\log n} )$ for deciding element distinctness (or the sign of a permutation).