Conference item icon

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

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

Actions


Access Document


Files:
Publisher copy:
10.1145/3055399.3055500

Authors


Oliveira, I More by this author
More by this author
Department:
Magdalen College
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

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP