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 Koucky, G Kozma, Z Lotker, MR Tuttle
Proceedings of the twentieth annual symposium on Parallelism in algorithms …, 2008
2192008
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
2092008
Power from random strings
E Allender, H Buhrman, M Koucký, D Van Melkebeek, D Ronneburger
SIAM Journal on Computing 35 (6), 1467-1493, 2006
962006
Amplifying lower bounds by means of self-reducibility
E Allender, M Koucký
Journal of the ACM (JACM) 57 (3), 1-36, 2010
742010
Universal traversal sequences with backtracking
M Koucký
Journal of Computer and System Sciences 65 (4), 717-726, 2002
742002
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
522011
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
502016
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
472011
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
46*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
352014
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
342011
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
342002
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
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
322016
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
322001
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
252005
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
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
232012
Derandomizing from random strings
H Buhrman, L Fortnow, M Koucký, B Loff
2010 IEEE 25th Annual Conference on Computational Complexity, 58-63, 2010
212010
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
Le système ne peut pas réaliser cette opération maintenant. Veuillez réessayer plus tard.
Articles 1–20