Search results
- 1.0352607 - MÚ 2011 RIV US eng J - Journal Article
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
R&D Projects: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Institutional research plan: CEZ:AV0Z10190503
Keywords : Circuit complexity * Distinguishing complexity * FewEXP * Formula size * Kolmogorov complexity
Subject RIV: BA - General Mathematics
Impact factor: 1.157, year: 2011
http://www.sciencedirect.com/science/article/pii/S0022000010000887
Permanent Link: http://hdl.handle.net/11104/0192081File Download Size Commentary Version Access Koucky.pdf 1 404.2 KB Publisher’s postprint require - 2.0352511 - MÚ 2011 RIV US eng J - Journal Article
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
R&D Projects: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Institutional research plan: CEZ:AV0Z10190503
Keywords : Circuit Complexity * Lower Bounds * Natural Proofs * Self-Reducibility * Time-Space Tradeoffs
Subject RIV: BA - General Mathematics
Impact factor: 3.375, year: 2010
http://dl.acm.org/citation.cfm?doid=1706591.1706594
Permanent Link: http://hdl.handle.net/11104/0192003File Download Size Commentary Version Access Koucky.pdf 1 249.6 KB Author’s postprint require - 3.0038960 - MÚ 2007 RIV US eng J - Journal Article
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
Institutional research plan: CEZ:AV0Z10190503
Keywords : Kolmogorov complexity * completeness * reductions
Subject RIV: BA - General Mathematics
Impact factor: 1.361, year: 2006
Permanent Link: http://hdl.handle.net/11104/0133162File Download Size Commentary Version Access Koucky.pdf 1 307.6 KB Publisher’s postprint require - 4.0038951 - MÚ 2007 RIV NL eng J - Journal Article
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
Institutional research plan: CEZ:AV0Z10190503
Keywords : Kolmogorov complexity * Kolmogorov random strings * completeness
Subject RIV: BA - General Mathematics
Impact factor: 0.582, year: 2006
Permanent Link: http://hdl.handle.net/11104/0133157File Download Size Commentary Version Access Koucky1.pdf 1 274.2 KB Publisher’s postprint require