Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness

Xin Lyu, Weihao Zhu

In the Element Distinctness problem, one is given an array $a_1,\dots ,a_n$ of integers from $[poly(n)]$ and is tasked to decide if $\{a_i\}$ are mutually distinct. Beame, Clifford…