COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Algorithms and Complexity Seminar > Polynomial-Time Pseudodeterministic Construction of Primes

## Polynomial-Time Pseudodeterministic Construction of PrimesAdd to your list(s) Download to your calendar using vCal - Igor Carboni Oliveira (University of Warwick)
- Tuesday 30 April 2024, 14:00-15:00
- Computer Laboratory, William Gates Building, Room SS03.
If you have a question about this talk, please contact Tom Gur. 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. Reference: https://eccc.weizmann.ac.il/report/2023/076/ This talk is part of the Algorithms and Complexity Seminar series. ## This talk is included in these lists:- Algorithms and Complexity Seminar
- All Talks (aka the CURE list)
- Cambridge talks
- Computer Laboratory, William Gates Building, Room SS03
- Department of Computer Science and Technology talks and seminars
- Interested Talks
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- ki287
Note that ex-directory lists are not shown. |
## Other listsInstitute Seminar Perspectives from Cambridge Assessment IMS-MRL External Seminar series## Other talksThe role of SARS-CoV-2 Membrane and Envelope proteins in protective immunity to COVID-19 Plant Sciences Seminar Restoring communication with intracortical brain-computer interfaces Accelerate lunchtime seminar series Policing Empires: Militarization, Race, and the Imperial Boomerang in Britain and the US Applications of proofs to network security |