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 } of 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 more general theorem about pseudodeterministic constructions. A property Q ⊆ {0,1} * is ϒ-dense if for large enough n , | Q ∩ {0,1} n | ≥ ϒ2 n . We show that for each c > 0 at least one of the following holds: (1) There is a pseudodeterministic polynomial time construction of a family { H n } of sets, H n ⊆ {0,1} n , such that for each (1/ n c )-dense property Q Ε DTIME ( n c ) and every large enough n , H n ∩ Q ≠ ∅ or (2) There is a deterministic sub-exponential time construction of a family { H ′ n } of sets, H ′ n ∩ {0,1} n , such that for each (1/ n c )-dense property Q Ε DTIME ( n c ) and for infinitely many values of n , H ′ n ∩ Q ≠ ∅. We provide further algorithmic applications that might be of independent interest. 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.

Authors

• Igor C. Oliveira 0001
• Rahul Santhanam

Keywords

• derandomization
• explicit constructions
• prime numbers
• pseudorandomness