Michal Koucky
Cited by
Cited by
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
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
Power from random strings
E Allender, H Buhrman, M Koucký, D Van Melkebeek, D Ronneburger
SIAM Journal on Computing 35 (6), 1467-1493, 2006
Amplifying lower bounds by means of self-reducibility
E Allender, M Koucký
Journal of the ACM (JACM) 57 (3), 1-36, 2010
Universal traversal sequences with backtracking
M Koucký
Journal of Computer and System Sciences 65 (4), 717-726, 2002
Approximating edit distance within constant factor in truly sub-quadratic time
D Chakraborty, D Das, E Goldenberg, M Koucký, M Saks
Journal of the ACM (JACM) 67 (6), 1-22, 2020
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
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
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
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
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
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
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
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
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
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
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
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
Tight lower bounds for the online labeling problem
J Bulánek, M Koucky, M Saks
SIAM Journal on Computing 44 (6), 1765-1797, 2015
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
The system can't perform the operation now. Try again later.
Articles 1–20