Výsledky vyhledávání
- 1.0352607 - MÚ 2011 RIV US eng J - Článek v odborném periodiku
Allender, E. - Koucký, Michal - Ronneburger, D. - Roy, S.
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.
Journal of Computer and System Sciences. Roč. 77, č. 1 (2011), s. 14-40. ISSN 0022-0000. E-ISSN 1090-2724
Grant CEP: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Circuit complexity * Distinguishing complexity * FewEXP * Formula size * Kolmogorov complexity
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.157, rok: 2011
http://www.sciencedirect.com/science/article/pii/S0022000010000887
Trvalý link: http://hdl.handle.net/11104/0192081Název souboru Staženo Velikost Komentář Verze Přístup Koucky.pdf 1 404.2 KB Vydavatelský postprint vyžádat - 2.0352511 - MÚ 2011 RIV US eng J - Článek v odborném periodiku
Allender, E. - Koucký, Michal
Amplifying lower bounds by means of self-reducibility.
Journal of the ACM. Roč. 57, č. 3 (2010), s. 1-36. ISSN 0004-5411. E-ISSN 1557-735X
Grant CEP: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Circuit Complexity * Lower Bounds * Natural Proofs * Self-Reducibility * Time-Space Tradeoffs
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 3.375, rok: 2010
http://dl.acm.org/citation.cfm?doid=1706591.1706594
Trvalý link: http://hdl.handle.net/11104/0192003Název souboru Staženo Velikost Komentář Verze Přístup Koucky.pdf 1 249.6 KB Autorský postprint vyžádat - 3.0038960 - MÚ 2007 RIV US eng J - Článek v odborném periodiku
Allender, E. - Buhrman, H. - Koucký, Michal - van Melkebeek, D. - Ronneburger, D.
Power from Random Strings.
[Síla náhodných řetízků.]
Siam Journal on Computing. Roč. 35, č. 6 (2006), s. 1467-1493. ISSN 0097-5397. E-ISSN 1095-7111
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Kolmogorov complexity * completeness * reductions
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.361, rok: 2006
Trvalý link: http://hdl.handle.net/11104/0133162Název souboru Staženo Velikost Komentář Verze Přístup Koucky.pdf 1 307.6 KB Vydavatelský postprint vyžádat - 4.0038951 - MÚ 2007 RIV NL eng J - Článek v odborném periodiku
Allender, E. - Buhrman, H. - Koucký, Michal
What can be efficiently reduced to the Kolmogorov-random strings?
[Co se dá efektivně zredukovat na Kolmogorovsky náhodné řetízky?]
Annals of Pure and Applied Logic. Roč. 138, č. 1 (2006), s. 2-19. ISSN 0168-0072. E-ISSN 1873-2461
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Kolmogorov complexity * Kolmogorov random strings * completeness
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.582, rok: 2006
Trvalý link: http://hdl.handle.net/11104/0133157Název souboru Staženo Velikost Komentář Verze Přístup Koucky1.pdf 1 274.2 KB Vydavatelský postprint vyžádat