Pseudodeterministic constructions in subexponential time

Igor Carboni Oliveira

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.