Hongxun Wu "Element distinctness, Pollard's rho, and PRG via Iterative restriction"
- Event Type
- Seminar/Symposium
- Sponsor
- Illinois Computer Science
- Location
- 3401 Siebel Center for Computer Science
- Virtual
- Join online
- Date
- Apr 10, 2023 11:00 am
- Cost
- Hongxun Wu (UC Berkeley)
- Contact
- Candice Steidinger
- steidin2@illinois.edu
- Views
- 73
- Originating Calendar
- Siebel School Speakers Calendar
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 .