Invited Speakers

Undergraduate Research Forum

Element Distinctness, Birthday Paradox, and 1-out Pseudorandom Graphs

Hongxun Wu

Tsinghua University

Abstract:
Element Distinctness is a fundamental computational problem: given an array of n input integers with O(log n) bit-length, decide whether or not all elements are pairwise distinct. In comparision model, the optimal time space tradeoff was resolved in the 80s. Specifically, with only O(polylog n) bits of memory, Õ(n^2) time pairwise comparision is necessary.
In RAM model, surprisingly, Beame, Clifford, and Machmouchi gave a Õ(n^{1.5})-time randomized algorithm for Element Distinctness using only O(log n) bits of working space. However, their algorithm assumes a random oracle (in particular, read-only random access to polynomially many random bits), and it was asked as an open question whether this assumption can be removed.
In this talk, we constructed a pseudorandom hash family based on iterative restrictions, which can replace this random oracle. This answers the open quesstion and makes the result by Beame et al. unconditional. This is joint work with Lijie Chen, Ce Jin, and Ryan Williams.

Bio:
Hongxun Wu recently recieved Bachelor's degree from Yao Class, Tsinghua. He is going to pursue PhD at UC Berkeley. His research interest is mainly in algorithm design and pseudorandomness.