Research Interests

Theoretical computer science - computational complexity, data structures and algorithms, combinatorics.

Project EPAC: Efficient approximation algorithms and circuit complexity

Project LBCAD: Lower bounds for combinatorial algorithms and dynamic problems

On-line Publications

Please note that many of the publications below are subject to copyright restrictions but you are free to use such publications for personal use.
Full list with links to published versions is available at DBLP.

• M. Bender, A. Conway, M. Farach-Colton, H. Komlós, M. Koucký, W. Kuszmaul, and M. Saks.
  Nearly Optimal List Labeling. FOCS 2024 (to appear)
  - arXiv:2405.00807, 2024.
  
  
• M. Koucký, M. Saks:
  Almost Linear Size Edit Distance Sketch.
  - 56th Annual ACM Symposium on the Theory of Computing, STOC'24, pp. 956-967, 2024.
  - arXiv:2406.11225, 2024.
  
  
• S. Bhattacharya and M. Koucký:
  Streaming k-Edit Approximate Pattern Matching via String Decomposition.
  - 50th International Colloquium on Automata, Languages and Programming, ICALP'23, pp. 22:1-22:14, 2023.
  - arXiv:2305.00615, 2023.
  
  
• M. Koucký and M. Saks:
  Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.
  - 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA'23, pp. 5203-5219, 2023.
  
  
• S. Bhattacharya and M. Koucký:
  Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching.
  - 55th Annual ACM Symposium on the Theory of Computing, STOC'23, pp. 219-232, 2023.
  - arXiv:2302.04475, 2023.
  
  
• P. Dvořák, M. Koucký, K. Král, and V. Slívová.
  Data Structures Lower Bounds and Popular Conjectures.
  - 29th Annual European Symposium on Algorithms, ESA'21, pp. 39:1-39:15, 2021.
  - arXiv:2102.09294, 2021.
  
  
• M. Koucký and K. Král.
  Sorting Short Integers.
  - 48th International Colloquium on Automata, Languages and Programming, ICALP'21, pp. 88:1-88:17, 2021
  - arXiv:2102.10027, 2021.
  
  
• P. Dvořák and M. Koucký.
  Barrington Plays Cards: The Complexity of Card-based Protocols.
  - 38th Symposium on Theoretical Aspects of Computer Science, STACS'21, pp. 26:1-26:17, 2021.
  - arXiv:2010.08445, 2020.
  
  
• S. Arunachalam, S. Chakraborty, M. Koucký, N. Saurabh, and R. de Wolf.
  Improved Bounds on Fourier Entropy and Min-Entropy.
  - ACM Transactions on Computation Theory 13(4): 22:1-22:40, 2021.
  - 37th Symposium on Theoretical Aspects of Computer Science, STACS'20, pp. 45:1-45:19, 2020.
  
  
• H. Buhrman, M. Christandl, M. Koucký, Z. Lotker, B. Patt-Shamir, and N. Vereshchagin.
  High entropy random selection protocols.
  - Algorithmica 83(2): 667-694, 2021.
  - 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.
  
  
• M. Koucký, V. Rödl, and N. Talebanfard.
  A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm.
  - Logical Methods in Computer Science 17(4), 2021.
  - arXiv:2105.06744, 2021.
  
  
• M. Koucký and M. Saks.
  Constant factor approximations to edit distance on far input pairs in nearly linear time
  - 52nd Annual ACM Symposium on the Theory of Computing, STOC'20, pp. 699-712, 2020.
  - arXiv:1904.05459, 2019.
  
  
• D. Chakraborty, D. Das, E. Goldenberg, M. Koucký, M. Saks.
  Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. rev 0
  - Journal of the ACM 67(6): 36:1-36:22, 2020.
  - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS'18, pp. 979-990, 2018, best paper award.
  
  
• S. Buss, V. Kabanets, A. Kolokolova, and M. Koucký.
  Expanders in VNC^1
  - Annals of Pure and Applied Logic 171(7): 102796, 2020.
  - Conference on Innovations in Theoretical Computer Science, ITCS'2017, pp. 31:1-31:26, 2017.
  
  
• 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'19, 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, 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.

Expository articles

• M. Koucký.
  Automata and Formal Languages: Shall we let them go?
  - Bulletin of the EATCS 140, 2023.
  
  
• M. Koucký.
  Sorting Short Integers: The Exposition.
  - Bulletin of the EATCS 135, 2021.
  
  
• M. Koucký.
  Circuit complexity of regular languages. Handbook of Automata Theory (I.) 2021: 493-523
  
  
• M. Koucký.
  Catalytic computation.
  - Bulletin of the EATCS 118 (2016).
  
  
• M. Koucký.
  A Brief Introduction to Kolmogorov Complexity.
  Lecture notes for KAM Spring School on Combinatorics, 2006.
  
  

On-line Manuscripts, Technical Reports and Thesis

• 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,

On-line presentations

Locally consistent decomposition of strings with applications to edit distance sketching. Computer Science and Discrete Mathematics Seminar, Institute for Advanced Study, Princeton, 2024.

Streaming k-edit approximate pattern matching via string decomposition. ICALP, Padeborn, 2023.

Journey with Eric Allender: From Turing machines to circuits, and back. Workshop: Lower Bounds, Learning, and Average-Case Complexity, Simons Institute, Berkeley 2023.

Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. SODA, Florence, 2023.

Zjemnělá složitost. Česká učená společnost, Praha, 2022.

Čas v počítači. Noc vědců, Praha, 2021.

Computing edit distance. CPM, Wroclaw, 2021.

O(1)-approximation of edit distance on far inputs in near linear time. online seminar, Hebrew University, Jerusalem, 2020.

Kolik paměti potřebujeme na vyhodnocení výrazu. Den otevřených dveří MFF UK, Praha, 2019.

Jak využít cizí paměť. Jeden den s informatikou a matematikou, MFF UK, Praha, 2019.

Approximating edit distance within constant factor in truly sub-quadratic time. TCS+, 2019.

Lower bounds for combinatorial algorithms for Boolean Matrix Multiplication. 2016.

Streaming algorithms for edit distance. Workshop: Processing Big Data Streams, Shonan, 2017.

Lower bounds and the physical reality. PIS, Praha, 2016.

Deset důdodů proč P=NP. Seminář: Filosofické problémy informatiky, Praha, 2015.

A New Approach to the Sensitivity Conjecture. ITCS, Weizmann Institute, Rehovot, 2015.

Catalytic Computation. Prague Gathering of Logicians, Prague, 2014.

The story of superconcentrators – the missing link. Seventh International Conference on Computability, Complexity and Randomness (CCR 2012), Cambridge, UK, 2012.

Are lower bounds hard to prove? Workshop: Synergies in Lower Bounds, Aarhus, 2011.

Pseudorandom generators for group products. STOC, San Jose, 2011.

A new characterization of ACC0 and probabilistic CC0. Workshop on Circuits, Logic, and Games, Dagstuhl, 2010.

Jak se pohybovat v rychle se měnícím světě: Doba pokrytí dynamických grafů. (How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)) STTI, Praha, 2009.

Winning concurrent reachability games requires doubly-exponential patience. LICS, Los Angeles, 2009.

Amplifying lower bounds by means of self-reducibility. CCC, Washington, DC, 2008. Longer version, Workshop on Computational Complexity of Discrete Problems, Dagstuhl, 2008.

High entropy random selection protocols. RANDOM, Princeton, 2007. Longer version, Tel Aviv, 2007.

Circuit complexity of regular languages. CiE, Siena, 2007.

Circuit lower bounds via Ehrenfeucht-Fraissé games. CCC, Praha, 2006.

Bounded-depth circuits: separating wires from gates. STOC, Baltimore, 2005.

Miscellaneous

Smart Ulist (UserList) for Novell NetWare 3.11+.

Hexadecimal file dump.

Check out the programming contest problem set archive.