We look forward to seeing you in person in 3401 Siebel Center or online on Monday, April 10th.
Abstract:
The element distinctness problem asks to determine whether an array of n input integers are distinct. Despite being a simple and fundamental computational task, its complexity in the low space RAM model, with only polylog(n)-sized working memory and random access to input, remains not fully understood. Beame, Clifford, and Machmouchi [FOCS'13] proposed an O(m sqrt(n)) time algorithm for this problem, drawing on ideas similar to Pollard's rho algorithm and assuming a random oracle as the hash function.
In our work, we eliminate the random oracle assumption by replacing f with a pseudorandom hash function f' constructed using iterative restriction. This function's seed fits within our polylog(n)-sized memory. In Pollard's rho algorithm, the hash function f generates a truly random 1-out graph with edges (v, f(v)). Starting from any vertex, a walk forms a rho-shaped cycle, which, by the birthday paradox, has length sqrt(n). Our pseudorandom hash function f' successfully fools this adaptive walk and, consequently, derandomizes the BCM algorithm.
Joint work with Lijie Chen, Ce Jin, and Ryan Williams. SODA '22. https://arxiv.org/abs/2111.01759 .
