Follow
Michal Koucky
Title
Cited by
Cited by
Year
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
2572008
Many random walks are faster than one
N Alon, C Avin, M Koucky, G Kozma, Z Lotker, MR Tuttle
Proceedings of the twentieth annual symposium on parallelism in algorithms …, 2008
2512008
Power from random strings
E Allender, H Buhrman, M Koucký, D Van Melkebeek, D Ronneburger
SIAM Journal on Computing 35 (6), 1467-1493, 2006
1552006
Amplifying lower bounds by means of self-reducibility
E Allender, M Koucký
Journal of the ACM (JACM) 57 (3), 1-36, 2010
1062010
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
862016
Universal traversal sequences with backtracking
M Koucký
Journal of Computer and System Sciences 65 (4), 717-726, 2002
842002
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
662011
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
652014
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
642011
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
562011
Constant factor approximations to edit distance on far input pairs in nearly linear time
M Koucký, M Saks
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing …, 2020
532020
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
53*2006
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
482020
Simulation theorems via pseudo-random properties
A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay
computational complexity 28, 617-659, 2019
432019
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
402002
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
402001
Towards a reverse newman’s theorem in interactive information complexity
J Brody, H Buhrman, M Koucký, B Loff, F Speelman, N Vereshchagin
Algorithmica 76, 749-781, 2016
392016
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
362009
Cover time and mixing time of random walks on dynamic graphs
C Avin, M Koucký, Z Lotker
Random Structures & Algorithms 52 (4), 576-596, 2018
352018
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
322005
The system can't perform the operation now. Try again later.
Articles 1–20