Michal Koucky

Cited by

	All	Since 2017
Citations	1676	734
h-index	22	14
i10-index	36	18

180

135

2003200420052006200720082009201020112012201320142015201620172018201920202021202212 18 16 34 17 51 60 76 84 108 104 115 101 114 137 129 150 168 134 14

Public access

View all

13 articles

2 articles

available

not available

Based on funding mandates

Co-authors

Harry BuhrmanGroup leader CWI & Distinguished Research Professor Univ. of Amsterdam & Founding Director QuSoftVerified email at cwi.nl
Eric AllenderRutgers UniversityVerified email at cs.rutgers.edu
Zvi LotkerProfessor of Communication Systems Engineering, Ben Gurion University of the NegevVerified email at bgu.ac.il
Chen AvinSchool of Electrical and Computer Engineering. Ben Gurion University of the NegevVerified email at cse.bgu.ac.il
Michael SaksRutgers University-New BrunswickVerified email at math.rutgers.edu
Diptarka ChakrabortySchool of Computing, National University of SingaporeVerified email at comp.nus.edu.sg
Elazar GoldenbergLecturer of Computer Science at the Academic College of Tel Aviv YaffoVerified email at mta.ac.il
Kristoffer Arnsfelt HansenAssociate Professor, Department of Computer Science, Aarhus UniversityVerified email at cs.au.dk
Bruno LoffUniversity of Porto and INESC-TecVerified email at fc.up.pt
Florian SpeelmanUniversity of Amsterdam, QuSoftVerified email at uva.nl
Lance FortnowIllinois Institute of TechnologyVerified email at iit.edu
Denis Theriendenis@cs.mcgill.caVerified email at elementai.com
Noga AlonPrinceton University and Tel Aviv UniversityVerified email at tau.ac.il
Sambuddha RoyUnaffiliated - Deep Learning Consultant/PractitionerVerified email at in.ibm.com
Peter Bro MiltersenFormer Professor of Computer Science at Aarhus UniversityVerified email at cs.au.dk
Prajakta NimbhorkarChennai Mathematical InstituteVerified email at cmi.ac.in
Arkadev ChattopadhyayAssociate Professor at Tata Institute of Fundamental ResearchVerified email at tifr.res.in
Elias TsigaridasINRIAVerified email at inria.fr
Justin GilmerGoogleVerified email at google.com
Richard CleveInstitute for Quantum Computing, University of WaterlooVerified email at uwaterloo.ca

Michal Koucky

Charles University, Prague

Verified email at iuuk.mff.cuni.cz

Computational Complexity Theoretical Computer Science


Title Sort by citations Sort by year Sort by 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	236	2008
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	235	2011
Power from random strings E Allender, H Buhrman, M Koucký, D Van Melkebeek, D Ronneburger SIAM Journal on Computing 35 (6), 1467-1493, 2006	118	2006
Amplifying lower bounds by means of self-reducibility E Allender, M Koucký Journal of the ACM (JACM) 57 (3), 1-36, 2010	88	2010
Universal traversal sequences with backtracking M Koucký Journal of Computer and System Sciences 65 (4), 717-726, 2002	77	2002
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	62	2016
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	61	2020
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	56	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	56	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	49*	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	45	2014
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	40	2011
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	37	2002
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	36	2001
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	35	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	33	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	30	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	28	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	24	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	24	2014

The system can't perform the operation now. Try again later.

Articles 1–20

Citations per year

Duplicate citations

Merged citations

Add co-authorsCo-authors

Follow this author

Cited by

Co-authors