Conference item

### Pseudodeterministic constructions in subexponential time

Abstract:

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 of...

Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

### Access Document

Files:
• (pdf, 559.7KB)
Publisher copy:
10.1145/3055399.3055500

### Authors

More by this author
Department:
Magdalen College
Role:
Author
Publisher:
Association for Computing Machinery Publisher's website
Publication date:
2017-06-05
Acceptance date:
2017-02-08
DOI:
Pubs id:
pubs:690037
URN:
uri:d5942583-3d49-491c-aef2-3541dc880423
UUID:
uuid:d5942583-3d49-491c-aef2-3541dc880423
Local pid:
pubs:690037
Keywords: