Search results
- 1.0318523 - MÚ 2009 RIV US eng C - Conference Paper (international conference)
Allender, E. - Koucký, Michal
Amplifying Lower Bounds by Means of Self-Reducibility.
[Zesilování dolních odhadů pomocí dolů samopřevoditelnosti.]
Proceedings of IEEE Conference on Computational Complexity 2008. Maryland: IEEE Computer Society Press, 2008, s. 31-40. ISBN 978-0-7695-3169-4.
[IEEE Conference on Computational Complexity 2008. College Park (US), 23.06.2008-26.06.2008]
R&D Projects: GA ČR GP201/07/P276
Institutional research plan: CEZ:AV0Z10190503
Keywords : circuit complexity * lower bounds * natural proofs
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0167916File Download Size Commentary Version Access Koucky.pdf 1 414.3 KB Publisher’s postprint require - 2.0038949 - MÚ 2007 RIV DE eng C - Conference Paper (international conference)
Allender, E. - Buhrman, H. - Koucký, Michal
What Can Be Efficiently Reduced to the K-random Strings?
[Co se dá efektivně zredukovat na Kolmogorovsky náhodné řetízky?]
Proceedings 21st International Symposium on Theoretical Aspects of Computer Science (STACS). Berlin: Springer-Verlag, 2004 - (Diekert, V.; Habib, M.), s. 584-595. Lecture Notes in Computer Science, 2996. ISBN 3-540-21236-1.
[Annual Symposium on Theoretical Aspects of Computer Science/21./. Montpellier (FR), 25.03.2004-27.03.2004]
Institutional research plan: CEZ:AV0Z1019905
Keywords : Kolmogorov complexity * Kolmogorov random strings * completeness
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0133155