# Pseudodeterministic Constructions in Subexponential Time

arXiv: https://arxiv.org/abs/1612.01817 · HTML: https://mlsanity.com/paper/1612.01817/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2016.

## Built on by (most cited first, 1 of 1)

- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (2023)

## Abstract (arXiv)

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 ∈ mathbbN 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 subseteq 0,1* is γ-dense if for large enough n, |Q cap 0,1n| ≥ γ 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 subseteq 0,1n, such that for each (1/nc)-dense property Q ∈ mathsfDTIME(nc) and every large enough n, Hn cap Q neq emptyset; or (2) There is a deterministic sub-exponential time construction of a family H'n of sets, H'n subseteq 0,1n, such that for each (1/nc)-dense property Q ∈ mathsfDTIME(nc) and for infinitely many values of n, H'n cap Q neq emptyset. 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.