Pseudodeterministic constructions in subexponential time

Conference item

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 {pn}n∈N of increasing primes and a randomized algorithm A running in expected sub-exponential time such that for each n, on input 1|pn|, A outputs pn 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. A property Q ⊆ {0, 1}* is γ-dense if for large enough n, |Q ⋂ {0, 1}n| ≥ γ2n. 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 {Hn} of sets, Hn ⊆ {0, 1}n, such that for each (1=nc)-dense property Q ∈ DTIME(n^c) and every large enough n, Hn ⋂ 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: Oliveira, I; Santhanam, R

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Host title: 49th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2017)
• Journal: 49th Annual ACM SIGACT Symposium on the Theory of Computing
• Publication date: 2017-06-01
• Acceptance date: 2017-02-08
• DOI: 10.1145/3055399.3055500
• Keywords: Explicit constructions; derandomization; prime numbers; pseudorandomness