Michal Koucky
Title
Cited by
Cited by
Year
Many random walks are faster than one
N Alon, C Avin, M Koucký, G Kozma, Z Lotker, MR Tuttle
Combinatorics, Probability and Computing 20 (4), 481-502, 2011
2092011
How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)
C Avin, M Koucký, Z Lotker
Automata, Languages and Programming, 121-132, 2008
2002008
Power from random strings
E Allender, H Buhrman, M Koucký, D Van Melkebeek, D Ronneburger
SIAM Journal on Computing 35 (6), 1467-1493, 2006
892006
Universal traversal sequences with backtracking
M Koucký
Journal of Computer and System Sciences 65 (4), 717-726, 2002
722002
Amplifying lower bounds by means of self-reducibility
E Allender, M Koucký
Journal of the ACM (JACM) 57 (3), 1-36, 2010
682010
Exact algorithms for solving stochastic games
KA Hansen, M Koucky, N Lauritzen, PB Miltersen, EP Tsigaridas
Proceedings of the forty-third annual ACM symposium on Theory of computing …, 2011
492011
Pseudorandom generators for group products
M Koucký, P Nimbhorkar, P Pudlák
Proceedings of the 43rd ACM Symposium on Theory of Computing (to appear), 2011
452011
What can be efficiently reduced to the Kolmogorov-random strings?
E Allender, H Buhrman, M Koucky
Annals of Pure and Applied Logic 138 (1-3), 2-19, 2006
44*2006
Streaming algorithms for embedding and computing edit distance in the low distance regime
D Chakraborty, E Goldenberg, M Koucký
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
342016
Winning concurrent reachability games requires doubly-exponential patience
KA Hansen, M Koucky, PB Miltersen
2009 24th Annual IEEE Symposium on Logic In Computer Science, 332-341, 2009
332009
Power from random strings
E Allender, H Buhrman, M Koucky, D Van Melkebeek, D Ronneburger
The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002 …, 2002
332002
Towards a reverse newman’s theorem in interactive information complexity
J Brody, H Buhrman, M Koucký, B Loff, F Speelman, N Vereshchagin
Algorithmica 76 (3), 749-781, 2016
312016
Time-space tradeoffs in the counting hierarchy
E Allender, M Koucky, D Ronneburger, S Roy, V Vinay
Proceedings 16th Annual IEEE Conference on Computational Complexity, 295-302, 2001
312001
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
E Allender, M Koucký, D Ronneburger, S Roy
Journal of Computer and System Sciences 77 (1), 14-40, 2011
302011
Computing with a full memory: catalytic space
H Buhrman, R Cleve, M Koucký, B Loff, F Speelman
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
292014
Bounded-depth circuits: separating wires from gates
M Koucký, P Pudlák, D Thérien
Proceedings of the thirty-seventh annual ACM symposium on Theory of …, 2005
262005
The hardness of being private
A Ada, A Chattopadhyay, SA Cook, L Fontes, M Koucký, T Pitassi
ACM Transactions on Computation Theory (TOCT) 6 (1), 1-24, 2014
242014
A new approach to the sensitivity conjecture
J Gilmer, M Koucký, ME Saks
Proceedings of the 2015 Conference on Innovations in Theoretical Computer …, 2015
212015
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
A Gál, KA Hansen, M Koucký, P Pudlák, E Viola
Proceedings of the forty-fourth annual ACM symposium on Theory of computing …, 2012
212012
Circuit lower bounds via Ehrenfeucht-Fraisse games
M Koucky, S Poloczek, C Lautemann, D Therien
21st Annual IEEE Conference on Computational Complexity (CCC'06), 12 pp.-201, 2006
212006
The system can't perform the operation now. Try again later.
Articles 1–20