Pseudodeterministic constructions in subexponential time
<p>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 tim...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Association for Computing Machinery
2017
|