Events

National Center for Supercomputing Applications master calendar

View Full Calendar

NCSA staff who would like to submit an item for the calendar can email newsdesk@ncsa.illinois.edu.

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
wifi event
Date
Apr 10, 2023   11:00 am  
Cost
Hongxun Wu (UC Berkeley)
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Views
26
Originating Calendar
Computer Science 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 .

link for robots only