Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PRIMES:
Reports tagged with primes:
TR16-196 | 5th December 2016
Igor Carboni Oliveira, Rahul Santhanam

#### Pseudodeterministic Constructions in Subexponential Time

We study {\it pseudodeterministic constructions}, i.e., randomized algorithms which output the {\it same solution} on most computation paths. We establish unconditionally that there is an infinite sequence $\{p_n\}_{n \in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input ... more >>>

ISSN 1433-8092 | Imprint