National Center for Supercomputing Applications WordPress Master Calendar

View Full Calendar

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

Hanlin Ren "Polynomial-Time Pseudodeterministic Construction of Primes"

Event Type
Seminar/Symposium
Sponsor
Illinois Computer Science
Location
3401 Siebel Center for Computer Science
Virtual
wifi event
Date
Jan 22, 2024   11:00 am  
Speaker
Hanlin Ren, University of Oxford
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Views
73
Originating Calendar
Siebel School Speakers Calendar

We look forward to seeing you in person in 3401 Siebel Center for Computer Science or online on Monday, January 22. 

Abstract: A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an *unconditional* polynomial-time randomized algorithm $B$ such that, for infinitely many values of $n$, $B(1^n)$ outputs a canonical $n$-bit prime $p_n$ with high probability.   More generally, we prove that for every dense property $Q$ of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying $Q$.  This improves upon a subexponential-time construction of Oliveira and Santhanam.

Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell, using a variant of the Shaltiel--Umans generator.

Based on joint work with Lijie Chen, Zhenjian Lu, Igor C. Oliveira and Rahul Santhanam.  FOCS 2023. arxiv.org/abs/2305.15140 .


link for robots only