Michal Koucky

Cited by

	All	Since 2020
Citations	2247	858
h-index	25	17
i10-index	48	24

220

110

165

2003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202514 19 14 31 16 51 63 80 72 109 107 110 102 112 135 141 163 202 149 173 161 162 10

Public access

View all

24 articles

0 articles

available

not available

Based on funding mandates

Co-authors

Harry BuhrmanChief Scientist Q Algorithms @ Quantinuum, Professor Univ. of Amsterdam & Founding Director QuSoftVerified email at quantinuum.com
Eric AllenderRutgers UniversityVerified email at cs.rutgers.edu
Michael SaksRutgers University-New BrunswickVerified email at math.rutgers.edu
Zvi LotkerProfessor In Bar Ilan UniversityVerified email at biu.ac.il
Bruno LoffLASIGE, Faculdade de Ciências da Universidade de LisboaVerified email at fc.up.pt
Diptarka ChakrabortySchool of Computing, National University of SingaporeVerified email at comp.nus.edu.sg
Chen AvinSchool of Electrical and Computer Engineering. Ben Gurion University of the NegevVerified email at cse.bgu.ac.il
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
Arkadev ChattopadhyayProfessor at Tata Institute of Fundamental ResearchVerified email at tifr.res.in
Florian SpeelmanUniversity of Amsterdam, QuSoftVerified email at uva.nl
Noga AlonPrinceton University and Tel Aviv UniversityVerified email at tau.ac.il
Peter Bro MiltersenFormer Professor of Computer Science at Aarhus UniversityVerified email at cs.au.dk
Lance FortnowIllinois Institute of TechnologyVerified email at iit.edu
Sambuddha RoyUnaffiliated - Deep Learning Consultant/PractitionerVerified email at in.ibm.com
Prajakta NimbhorkarChennai Mathematical InstituteVerified email at cmi.ac.in
Elias TsigaridasINRIAVerified email at inria.fr
Richard CleveInstitute for Quantum Computing, University of WaterlooVerified email at uwaterloo.ca
Justin GilmerGoogleVerified email at google.com
Matthias ChristandlUniversity of CopenhagenVerified email at math.ku.dk

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	257	2008
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	251	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	158	2006
Amplifying lower bounds by means of self-reducibility E Allender, M Koucký Journal of the ACM (JACM) 57 (3), 1-36, 2010	108	2010
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	91	2016
Universal traversal sequences with backtracking M Koucký Journal of Computer and System Sciences 65 (4), 717-726, 2002	88	2002
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	68	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	67	2014
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	64	2011
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	58	2011
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	54	2020
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	49	2020
Simulation theorems via pseudo-random properties A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay computational complexity 28, 617-659, 2019	43	2019
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	40	2016
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	40	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	40	2001
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	37	2009
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	36	2018
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	34	2005

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

Cited by

Co-authors