National Center for Supercomputing Applications master calendar

View Full Calendar

NCSA staff who would like to submit an item for the calendar can email

Hongxun Wu "Element distinctness, Pollard's rho, and PRG via Iterative restriction"

Event Type
Illinois Computer Science
3401 Siebel Center for Computer Science
wifi event
Apr 10, 2023   11:00 am  
Hongxun Wu (UC Berkeley)
Candice Steidinger
Originating Calendar
Computer Science Speakers Calendar

We look forward to seeing you in person in 3401 Siebel Center or online on Monday, April 10th. 


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. .

link for robots only