BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Polynomial-Time Pseudodeterministic Construction of Primes - Igor 
 Carboni Oliveira (University of Warwick)
DTSTART:20240430T130000Z
DTEND:20240430T140000Z
UID:TALK212335@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:A randomized algorithm for a search problem is pseudodetermini
 stic if it\nproduces a fixed canonical solution to the search problem with
  high\nprobability. In their seminal work on the topic\, Gat and Goldwasse
 r posed\nas their main open problem whether prime numbers can be pseudodet
 erministically\nconstructed in polynomial time.\n\nWe provide a positive s
 olution to this question in the infinitely-often\nregime. In more detail\,
  we give an unconditional polynomial-time\nrandomized algorithm B such tha
 t\, for infinitely many values of n\, B(1^n)\noutputs a canonical n-bit pr
 ime p_n with high probability. More generally\,\nwe prove that for every d
 ense property Q of strings that can be decided in\npolynomial time\, there
  is an infinitely-often pseudodeterministic\npolynomial-time construction 
 of strings satisfying Q. This improves upon a\nsubexponential-time constru
 ction of Oliveira and Santhanam.\n\nOur construction uses several new idea
 s\, including a novel bootstrapping\ntechnique for pseudodeterministic con
 structions\, and a quantitative\noptimization of the uniform hardness-rand
 omness framework of Chen and\nTell\, using a variant of the Shaltiel-Umans
  generator.\n\nReference: https://eccc.weizmann.ac.il/report/2023/076/
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR