Search results
- 1.0336102 - MÚ 2010 RIV US eng C - Conference Paper (international conference)
Hansen, K.A. - Koucký, Michal
A new characterization of ACC(0) and probabilistic CC0.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity. Los Alamitos: IEEE Computer Society, 2009, s. 27-34. ISBN 978-0-7695-3717-7. ISSN 1093-0159.
[24th Annual IEEE Conference on Computational Complexity. Paris (FR), 15.07.2009-18.07.2009]
R&D Projects: GA ČR GP201/07/P276; GA AV ČR IAA100190902; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : bounded depth circuits * counting circuits
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0180415File Download Size Commentary Version Access Koucky.pdf 1 343.6 KB Publisher’s postprint require - 2.0336087 - MÚ 2010 RIV US eng C - Conference Paper (international conference)
Hansen, K.A. - Koucký, Michal - Miltersen, P.B.
Winning concurrent reachability games requires doubly-exponential patience.
Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LISC 2009. Los Angeles: IEEE Computer Society, 2009, s. 332-341. ISBN 978-0-7695-3746-7. ISSN 1043-6871.
[24th Annual IEEE Symposium on Logic in Computer Science. Los Angeles (US), 11.08.2009-14.08.2009]
R&D Projects: GA ČR GP201/07/P276; GA AV ČR IAA100190902; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : concurrent reachability game * patience * winning strategies
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0180404File Download Size Commentary Version Access Koucky1.pdf 1 284 KB Publisher’s postprint require - 3.0318535 - MÚ 2009 RIV DE eng C - Conference Paper (international conference)
Alon, N. - Avin, Ch. - Koucký, Michal - Kozma, G. - Lotker, Z. - Tuttle, M.R.
Many random walks are faster than one.
[Mnoho náhodných procházek je rychlejších než jedna.]
Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2008. Mnichov: ACM, 2008 - (Meyer, F.; Shavit, N.), s. 119-128. ISBN 978-1-59593-973-9.
[Annual ACM Symposium on Parallel Algorithms and Architectures SPAA 2008/20./. Mnichov (DE), 14.06.2008-16.06.2008]
R&D Projects: GA ČR GP201/07/P276
Institutional research plan: CEZ:AV0Z10190503
Keywords : random walks * cover time * speed-up
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0004967File Download Size Commentary Version Access Koucky1.pdf 1 300.4 KB Author’s postprint require - 4.0318526 - MÚ 2009 RIV US eng C - Conference Paper (international conference)
Buhrman, H. - Koucký, Michal - Vereshchagin, N.K.
Randomised Individual Communication Complexity.
[Pravděpodobnostní individuální komunikační složitosti.]
Proceedings of IEEE Conference on Computational Complexity 2008. Maryland: IEEE Computer Society Press, 2008, s. 321-331. 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 : randomized individual communication complexity * round complexity
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0167919File Download Size Commentary Version Access Koucky3.pdf 1 449.9 KB Publisher’s postprint require - 5.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 - 6.0318518 - MÚ 2009 RIV DE eng C - Conference Paper (international conference)
Avin, Ch. - Koucký, Michal - Lotker, Z.
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs).
[Jak prohledávat rychle se měnící svět ( Doba pokrytí vyvíjejícího se grafu jednoduchou náhodnou procházkou).]
Proceedings of 35th International Colloquium on Automata, Languages and Programming, ICALP 2008. Berlin: Springer, 2008 - (Aceto, L.; Damgárd, I.; Goldberg, L.; Halldórsson, M.; Ingólfsdóttir, A.; Walukiewicz, I.), s. 121-132. LNCS, 5125. ISBN 978-3-540-70574-1.
[International Colloquium on Automata, Languages and Programming, ICALP 2008/35./. Reykjavik (IS), 07.07.2008-11.07.2008]
R&D Projects: GA ČR GP201/07/P276
Institutional research plan: CEZ:AV0Z10190503
Keywords : random walks * cover time * evolving graphs
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0004965File Download Size Commentary Version Access Koucky2.pdf 1 495 KB Publisher’s postprint require - 7.0090045 - MÚ 2008 RIV DE eng C - Conference Paper (international conference)
Buhrman, H. - Christandl, M. - Koucký, Michal - Lotker, Z. - Patt-Shamir, B. - Vereshchagin, N.K.
High Entropy Random Selection Protocols.
[Protokoly pro výběr náhodného řetězce s velkou entropií.]
Proceedings of 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007, and 11th International Workshop on Randomization and Computation, RANDOM 2007, RANDOM-APPROX 2007. Berlin: Springer-Verlag, 2007 - (Charikar, M.; Jansen, K.; Reingold, O.; Rolim, J.), s. 366-379. Lecture Notes in Computer Science, 4627. ISBN 978-3-540-74207-4.
[International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/10./, and International Workshop on Randomization and Computation/11./, RANDOM-APPROX 2007. Princeton (US), 20.08.2007-22.08.2007]
R&D Projects: GA ČR GA201/05/0124; GA ČR GP201/07/P276
Institutional research plan: CEZ:AV0Z10190503
Keywords : random string selection * cryptography * Kakeya problem
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0151067File Download Size Commentary Version Access Koucky.pdf 1 445.5 KB Publisher’s postprint require - 8.0089758 - MÚ 2008 RIV RU eng C - Conference Paper (international conference)
Buhrman, H. - Fortnow, L. - Koucký, Michal - Rogers, J.D. - Vereshchagin, N.K.
Inverting Onto Functions and Polynomial Hierarchy.
[Invertování projektivních funkcí a polynomiální hierarchie.]
Proceedings of International Computer Science Symposium in Russia, CSR 2007. Berlin: Springer-Verlag, 2007 - (Diekert, V.; Volkov, M.; Voronkov, A.), s. 92-103. Lecture Notes in Computer Science, 4649. ISBN 978-3-540-74509-9.
[International Computer Science Symposium in Russia, CSR 2007. Jekaterinburg (RU), 03.09.2007-07.09.2007]
R&D Projects: GA ČR GA201/05/0124; GA ČR GP201/07/P276
Institutional research plan: CEZ:AV0Z10190503
Keywords : one-way functions * polynomial hierarchy * Kolmogorov generic oracles
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0150859File Download Size Commentary Version Access Koucky1.pdf 1 211.9 KB Publisher’s postprint require - 9.0089749 - MÚ 2010 RIV DE eng C - Conference Paper (international conference)
Koucký, Michal
Circuit complexity of regular languages.
[Obvodová složitost regulárních jazyků.]
proceedings of the 3rd Conference on Computability in Europe, CiE 2007. Heidelberg: Springer-Verlag, 2007 - (Cooper, S.; Loewe, B.; Sorbi, A.), s. 426-435. ISBN 978-3-540-73000-2.
[Conference on Computability in Europe/3./. Siena (IT), 18.06.2007-23.06.2007]
R&D Projects: GA ČR GA201/05/0124; GA ČR GP201/07/P276
Institutional research plan: CEZ:AV0Z10190503
Keywords : regular languages * circuit complexity
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0150854File Download Size Commentary Version Access Koucky3.pdf 1 358.1 KB Publisher’s postprint require