Pseudodeterministic Constructions in Subexponential Time

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10369837" target="_blank" >RIV/00216208:11320/17:10369837 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1145/3055399.3055500" target="_blank" >http://dx.doi.org/10.1145/3055399.3055500</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3055399.3055500" target="_blank" >10.1145/3055399.3055500</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Pseudodeterministic Constructions in Subexponential Time

Popis výsledku v původním jazyce

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 of increasing primes and a randomized algorithm running in expected sub-exponential time such that for each , on input , outputs with probability . 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 is -dense if for large enough , . We show that for each at least one of the following holds: (1) There is a pseudodeterministic polynomial time construction of a family of sets, , such that for each -dense property and every large enough , ; or (2) There is a deterministic sub-exponential time construction of a family of sets, , such that for each -dense property and for infinitely many values of , . 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.

Název v anglickém jazyce

Pseudodeterministic Constructions in Subexponential Time

Popis výsledku anglicky

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 of increasing primes and a randomized algorithm running in expected sub-exponential time such that for each , on input , outputs with probability . 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 is -dense if for large enough , . We show that for each at least one of the following holds: (1) There is a pseudodeterministic polynomial time construction of a family of sets, , such that for each -dense property and every large enough , ; or (2) There is a deterministic sub-exponential time construction of a family of sets, , such that for each -dense property and for infinitely many values of , . 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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017

ISBN

978-1-4503-4528-6

ISSN

—

e-ISSN

neuvedeno

Počet stran výsledku

13

Strana od-do

665-677

Název nakladatele

Association for Computing Machinery

Místo vydání

Kanada

Místo konání akce

Montreal, Kanada

Datum konání akce

19. 6. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—