- M. Koucký, V. Rödl, and N. Talebanfard.
**A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm.**

- ECCC Tech Rep. TR19-181, 2019.

- M. Koucký and M. Saks.
**Constant factor approximations to edit distance on far input pairs in nearly linear time**

- arXiv:1904.05459, 2019.

- D. Chakraborty, D. Das, and M. Koucký.
**Approximate Online Pattern Matching in Sublinear Time.**

-*39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science*, FSTTCS'19, pp. 10:1-10:15, 2019.

- P. Hubáček, M. Koucký, K. Král, and V. Slívová.
**Stronger Lower Bounds for Online ORAM.**

-*17th Theory of Cryptography Conference*, TCC 2019, pp. 264-284, 2019.

- A. Chattopadhyay, M. Koucký, B. Loff and S. Mukhopadhyay.
**Simulation Theorems via Pseudo-random Properties.**

-*Computational Complexity*, 28(4): 617-659, 2019.

- earlier version: ECCC Tech Rep. TR17-14, 2017.

- M. Babka, J. Bulánek, V. Čunát, M. Koucký, and M. Saks.
**On Online Labeling with Polynomially Many Labels.**

-*SIAM Journal on Discrete Mathematics*, 33(3): 1175-1193, 2019.

-*20th Annual European Symposium on Algorithms*, ESA'12, pp. 121-132, 2012.

- D. Chakraborty, D. Das, E. Goldenberg, M. Koucký, M. Saks.
**Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time.**rev 0

-*59th Annual IEEE Symposium on Foundations of Computer Science*, FOCS'18, pp. 979-990, 2018,*best paper award*.

- D. Chakraborty, D. Das, M. Koucký, N. Saurabh.
**Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity**

-*26th Annual European Symposium on Algorithms*, ESA'18, 12:1-12:15, 2018.

- arXiv:1712.01834, 2017.

- A. Chattopadhyay, M. Koucký, B. Loff and S. Mukhopadhyay.
**Simulation Beats Richness: New Data-Structure Lower Bounds.**

-*50th Annual ACM Symposium on the Theory of Computing*, STOC'18, pp. 1013-1020, 2018.

- ECCC Tech Rep. TR17-170, 2017.

- D. Das, M. Koucký, and M. Saks.
**Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication.**

-*35th Symposium on Theoretical Aspects of Computer Science*, STACS'18, pp. 23:1-23:14, 2018.

- C. Avin, M. Koucký, and Z. Lotker.
**How to explore a fast-changing world (cover time of a simple random walk on evolving graphs).**

-*Random Structures and Algorithms*, 52(4): 576-596, 2018.

-*35th International Colloquium on Automata, Languages and Programming, Part I*, ICALP'08, pp. 121-132, 2008.

- H. Buhrman, M. Koucký, B. Loff, F. Speelman.
**Catalytic Space: Non-determinism and Hierarchy.**

-*Theory of Computing Systems*, 62(1): 116-135, 2018.

-*33rd Symposium on Theoretical Aspects of Computer Science*, STACS'16, pp. 24:1-24:13, 2016.

- A. Chattopadhyay, P. Dvořák, M. Koucký, B. Loff and S. Mukhopadhyay
**Lower Bounds for Elimination via Weak Regularity.**

-*34th Symposium on Theoretical Aspects of Computer Science*, STACS'17, pp. 21:1-21:14, 2017.

- S. Buss, V. Kabanets, A. Kolokolova, and M. Koucký.
**Expanders in VNC^1**

-*Conference on Innovations in Theoretical Computer Science*, ITCS'2017, pp. 31:1-31:26, 2017.

- D. Chakraborty, E. Goldenberg, M. Koucký.
**Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees.**

- arXiv:1607.03718, 2016.

- J. Brody, H. Buhrman, M. Koucký, B. Loff, F. Speelman, and N. Vereshchagin
**Towards a Reverse Newman's Theorem in Interactive Information Complexity.**

-*Algorithmica*76(3): 749-781, 2016.

-*28th Annual IEEE Conference on Computational Complexity*, CCC'13, pp. 24-33, 2013.

- K. Arnsfelt Hansen, R. Ibsen-Jensen, M. Koucký.
**The Big Match in Small Space.**

-*9th International Symposium on Algorithmic Game Theory*, SAGT'2016, pp. 64-76, 2016,*best paper award*.

- M. Koucký.
**Catalytic computation.**

-*Bulletin of the EATCS*118 (2016).

- D. Chakraborty, E. Goldenberg, M. Koucký.
**Streaming algorithms for embedding and computing edit distance in the low distance regime.**

-*48th Annual ACM Symposium on Theory of Computing*, STOC'16, pp. 712-725.

- ECCC Tech Rep. TR15-111, 2015 (previous versions).

- J. Bulánek, M. Koucký, and M. Saks.
**Tight lower bounds for the online labeling problem.**

-*SIAM Journal on Computing*, 44(6):1765-1797, 2015.

-*44th Annual ACM Symposium on Theory of Computing*, STOC'12, pp. 1185-1198, 2012.

- V. Girard, M. Koucký, P. McKenzie.
**Nonuniform catalytic space and the direct sum for space.**

- ECCC Tech Rep. TR15-138, 2015.

- J.Gilmer, M.Koucký, M. Saks.
**A New Approach to the Sensitivity Conjecture.**

-*Conference on Innovations in Theoretical Computer Science*, ITCS'2015, pp. 247-254, 2015.

- H. Buhrman, E. Cleve, M. Koucký, B. Loff, F. Speelman.
**Computing with a full memory: Catalytic space.**

-*46th Annual ACM Symposium on Theory of Computing*, STOC'14, pp. 857-866, 2014.

- A. Ada, A. Chattopadhyay, S. A. Cook, L. Fontes, M. Koucký, and T. Pitassi.
**The Hardness of Being Private.**

-*ACM Transactions on Computation Theory*, 6(1):1:1-1:24, 2014.

-*27th Annual IEEE Conference on Computational Complexity*, CCC'12, pp. 192-202, 2012.

- A. Gál, K.A. Hansen, M. Koucký, P. Pudlák, and E. Viola.
**Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.**

-*IEEE Transactions on Information Theory*59(10): 6611-6627, 2013.

-*44th Annual ACM Symposium on Theory of Computing*, STOC'12, pp. 479-494, 2012.

- J. Bulánek, M. Koucký, and M. Saks.
**On Randomized Online Labeling with Polynomially Many Labels.**

-*40th International Colloquium on Automata, Languages and Programming, Part I*, ICALP'13, pp. 291-302, 2013.

- M. Babka, J. Bulánek, V. Čunát, M. Koucký, and M. Saks.
**On Online Labeling with Polynomially Many Labels.**

-*20th Annual European Symposium on Algorithms*, ESA'12, pp. 121-132, 2012.

- N. Alon, C. Avin, M. Koucký, G. Kozma, Z. Lotker, and M.R. Tuttle.
**Many random walks are faster than one.**

-*Combinatorics Probability and Computing*, 20(4):481-502, 2011.

-*20th Annual Symposium on Parallelism in Algorithms and Architectures*, SPAA'08, pp. 119-128, 2008.

- E. Allender, M. Koucký, D. Ronneburger, and S. Roy.
**The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.**

-*Journal of Computer and System Sciences*, 77:14-40, 2011.

- Partially based on**Derandomization and distinguishing complexity.**CCC'03, pp. 209-220, 2003.

- K. A. Hansen, M. Koucký, N. Lauritzen, P. B. Miltersen, and E. P. Tsigaridas.
**Exact algorithms for solving stochastic games.**

-*43rd Annual ACM Symposium on Theory of Computing*, STOC'11, pp. 205-214, 2011.

- M. Koucký, P. Nimbhorkar, and P. Pudlák.
**Pseudorandom generators for group products.**

-*43rd Annual ACM Symposium on Theory of Computing*, STOC'11, pp. 263-272, 2011.

- E. Allender and M. Koucký.
**Amplifying lower bounds by means of self-reducibility.**

-*Journal of the ACM*, 57:14:1-14:36, 2010.

-*23rd Annual IEEE Conference on Computational Complexity*, CCC'08, pp. 31-40, 2008.

- H. Buhrman, L. Fortnow, M. Koucký, and B. Loff.
**Derandomizing from random strings.**

-*25th Annual IEEE Conference on Computational Complexity*, CCC'10, pp. 58-63, 2010.

- K. A. Hansen, M. Koucký, and P. B. Miltersen.
**Winning concurrent reachability games requires doubly-exponential patience.**

-*24th Annual IEEE Symposium on Logic In Computer Science*, LICS'09, pp. 332-341, 2009.

- K. A. Hansen and M. Koucký.
**A new characterization of ACC0 and probabilistic CC0.**

-*Computational Complexity*(special issue for CCC'09), 19:211-234, 2010.

-*24th Annual IEEE Conference on Computational Complexity*, CCC'09, pp. 27-34, 2009.

- M. Koucký.
**Circuit complexity of regular languages.**

-*Theory of Computing Systems*, 45:865-879, 2009.

- Prelimary version an invited paper in*Proceedings of the 3rd conference on Computability in Europe: Computation and Logic in the Real World*, CiE'07, pp. 426-435, 2007.

- H. Buhrman, L. Fortnow, M. Koucký, J. D. Rogers, and N. Vereshchagin.
**Does the polynomial hierarchy collapse if onto functions are invertible?**

-*Theory of Computing Systems*(special issue for CSR'07), 46:143-156, 2009.

- Preliminary version:**Inverting onto functions and polynomial hierarchy.***Second International Symposium on Computer Science in Russia*, CSR'07, pp. 92-103, 2007.

- H. Buhrman, M. Koucký, and N. Vereshchagin.
**Randomised individual communication complexity.**

-*23rd Annual IEEE Conference on Computational Complexity*, CCC'08, pp. 321-331, 2008.

- A. Gál, M. Koucký, and P. McKenzie.
**Incremental branching programs.**

-*Theory of Computing Systems*(special issue for CSR'06), 43:159-184, 2008.

-*First International Computer Science Symposium in Russia*, CSR'06, pp. 178-190, 2006.

- H. Buhrman, M. Christandl, M. Koucký, Z. Lotker, B. Patt-Shamir, and N. Vereshchagin.
**High entropy random selection protocols.**

-*10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization: Algorithms and Techniques*, APPROX'07/RANDOM'07, pp. 366-379, 2007.

- A. Chattopadhyay, A. Krebs, M. Koucký, M. Szegedy, P. Tesson, and D. Thérien.
**Languages with bounded multiparty communication complexity.**

-*24th Annual Conference on Theoretical Aspects of Computer Science*, STACS'07, pp. 500-511, 2007.

- M. Koucký, C. Lautemann, S. Poloczek, and D. Thérien.
**Circuit lower bounds via Ehrenfeucht-Fraissé games.**

-*21st Annual IEEE Conference on Computational Complexity*, CCC'06, pp. 190-201, 2006.

- E. Allender, H. Buhrman, M. Koucký, D. van Melkebeek, and D. Ronneburger.
**Power from random strings.**

-*SIAM Journal on Computing*, 35:1467-1493, 2006.

-*43rd Symposium on Foundations of Computer Science*, FOCS'02, pp. 669-678, 2002.

- E. Allender, H. Buhrman, and M. Koucký.
**What can be efficiently reduced to the Kolmogorov-random strings?**

-*Annals of Pure and Applied Logic*, 138(1-3):2-19, 2006.

-*21st Annual Symposium on Theoretical Aspects of Computer Science*, STACS'04, pp. 584-595, 2004.

- M. Koucký, P. Pudlák, and D. Thérien.
**Bounded-depth circuits: separating wires from gates.**

-*37th Annual ACM Symposium on Theory of Computing*, STOC'05, pp. 257-265, 2005.

- E. Allender, M. Koucký, R. Ronneburger, and S. Roy.
**Derandomization and distinguishing complexity.**

-*18th Annual IEEE Conference on Computational Complexity*, CCC'03, pp. 209-220, 2003.

- M. Koucký.
**Log-space constructible universal traversal sequences for cycles of length O(n^4.03).**

-*Theoretical Computer Science*(special issue for COCOON'01), 296:117-144, 2003.

-*7th Annual International Conference on Computing and Combinatorics*, COCOON'01, pp. 11-20, 2001.

- M. Koucký.
**Universal traversal sequences with backtracking.**

-*Journal of Computer and System Sciences*(special issue for CCC'01), 65:717-726, 2002.

-*16th Annual IEEE Conference on Computational Complexity*, CCC'01, pp. 21-26, 2001.

- E. Allender, M. Koucký, D. Ronneburger, S. Roy, and V. Vinay.
**Time-space tradeoffs in the counting hierarchy.**

-*16th Annual IEEE Conference on Computational Complexity*, CCC'01, pp. 295-302, 2001.

- M. Koucký.
**A Brief Introduction to Kolmogorov Complexity.**

Lecture notes for KAM Spring School on Combinatorics, 2006.

- M. Koucký.
**On traversal and exploration sequences.**

DIMACS Technical Report 2003-41, 2003.

- M. Koucký.
**On traversal sequences, exploration sequences and completeness of Kolmogorov random strings.***Ph.D. Thesis*, Rutgers University, 2003.

- M. Koucký.
**Marking One-Way Multihead Finite Automata.***Master Thesis*(*in Czech*), Charles University, May 1998,