Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions

Lijie Chen, Ce Jin, R. Ryan Williams +1

We consider low-space algorithms for the classic Element Distinctness problem: given an array of $n$ input integers with $O(\log n)$ bit-length, decide whether or not all elements…