Michal Koucky
Michal Koucky
Charles University, Prague
Adresse e-mail validée de iuuk.mff.cuni.cz
Titre
Citée par
Citée par
Année
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
2272011
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
2272008
Power from random strings
E Allender, H Buhrman, M Koucký, D Van Melkebeek, D Ronneburger
SIAM Journal on Computing 35 (6), 1467-1493, 2006
1052006
Amplifying lower bounds by means of self-reducibility
E Allender, M Koucký
Journal of the ACM (JACM) 57 (3), 1-36, 2010
802010
Universal traversal sequences with backtracking
M Koucký
Journal of Computer and System Sciences 65 (4), 717-726, 2002
752002
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
552016
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
542011
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
532011
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
47*2006
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
382014
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
372002
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
362011
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
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
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
332001
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
282005
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
252012
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
Circuit lower bounds via Ehrenfeucht-Fraisse games
M Koucky, S Poloczek, C Lautemann, D Thérien
21st Annual IEEE Conference on Computational Complexity (CCC'06), 12 pp.-201, 2006
222006
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
212020
Le système ne peut pas réaliser cette opération maintenant. Veuillez réessayer plus tard.
Articles 1–20