Pseudodeterministic Constructions in Subexponential Time

We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infinite sequence {p_n}_n of increasing primes and a randomized algorithm A running in expected sub-exponential time such that for each n, on input 1^{|p_n|}, A outputs p_n with probability 1. In other words, our result provides a pseudodeterministic construction of primes in sub-exponential time which works infinitely often

This result follows from a much more general theorem about pseudodeterministic constructions. Perhaps intriguingly, while our main results are unconditional, they have a non-constructive element, arising from a sequence of applications of the hardness versus randomness paradigm.

(This is joint work with Rahul Santhanam.)