| 2026 | ICALP | Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric. | Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., Michal Kouck |
| 2026 | STOC | The Natural Proofs Barrier against Data-Structure Lower-Bounds. | Michal Kouck, Bruno Loff, Tulasimohan Molli, Michael E. Saks |
| 2025 | FOCS | Collapsing Catalytic Classes. | Michal Kouck, Ian Mertz, Edward Pyne, Sasha Sami |
| 2024 | FOCS | Nearly Optimal List Labeling. | Michael A. Bender, Alex Conway, Martn Farach-Colton, Hanna Komls, Michal Kouck, William Kuszmaul, Michael E. Saks |
| 2024 | STOC | Almost Linear Size Edit Distance Sketch. | Michal Kouck, Michael E. Saks |
| 2023 | ICALP | Streaming k-Edit Approximate Pattern Matching via String Decomposition. | Sudatta Bhattacharya, Michal Kouck |
| 2023 | SODA | Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. | Michal Kouck, Michael E. Saks |
| 2023 | STOC | Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching. | Sudatta Bhattacharya, Michal Kouck |
| 2021 | CPM | Computing Edit Distance (Invited Talk). | Michal Kouck |
| 2021 | ESA | Data Structures Lower Bounds and Popular Conjectures. | Pavel Dvork, Michal Kouck, Karel Krl, Veronika Slvov |
| 2021 | ICALP | Sorting Short Integers. | Michal Kouck, Karel Krl |
| 2021 | STACS | Barrington Plays Cards: The Complexity of Card-Based Protocols. | Pavel Dvork, Michal Kouck |
| 2020 | STOC | Constant factor approximations to edit distance on far input pairs in nearly linear time. | Michal Kouck, Michael E. Saks |
| 2020 | STACS | Improved Bounds on Fourier Entropy and Min-Entropy. | Srinivasan Arunachalam, Sourav Chakraborty, Michal Kouck, Nitin Saurabh, Ronald de Wolf |
| 2019 | TCC | Stronger Lower Bounds for Online ORAM. | Pavel Hubcek, Michal Kouck, Karel Krl, Veronika Slvov |
| 2018 | ESA | Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. | Diptarka Chakraborty, Debarati Das, Michal Kouck, Nitin Saurabh |
| 2018 | FOCS | Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. | Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Kouck, Michael E. Saks |
| 2018 | STOC | Simulation beats richness: new data-structure lower bounds. | Arkadev Chattopadhyay, Michal Kouck, Bruno Loff, Sagnik Mukhopadhyay |
| 2018 | STACS | Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. | Debarati Das, Michal Kouck, Michael E. Saks |
| 2017 | STACS | Lower Bounds for Elimination via Weak Regularity. | Arkadev Chattopadhyay, Pavel Dvork, Michal Kouck, Bruno Loff, Sagnik Mukhopadhyay |
| 2016 | STOC | Streaming algorithms for embedding and computing edit distance in the low distance regime. | Diptarka Chakraborty, Elazar Goldenberg, Michal Kouck |
| 2016 | STACS | Catalytic Space: Non-determinism and Hierarchy. | Harry Buhrman, Michal Kouck, Bruno Loff, Florian Speelman |
| 2016 | SAGT | The Big Match in Small Space - (Extended Abstract). | Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Michal Kouck |
| 2014 | STOC | Computing with a full memory: catalytic space. | Harry Buhrman, Richard Cleve, Michal Kouck, Bruno Loff, Florian Speelman |
| 2013 | ICALP | On Randomized Online Labeling with Polynomially Many Labels. | Jan Bulnek, Michal Kouck, Michael E. Saks |
| 2012 | ESA | On Online Labeling with Polynomially Many Labels. | Martin Babka, Jan Bulnek, Vladimr Cunt, Michal Kouck, Michael E. Saks |
| 2012 | STOC | Tight lower bounds for the online labeling problem. | Jan Bulnek, Michal Kouck, Michael E. Saks |
| 2012 | STOC | Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. | Anna Gl, Kristoffer Arnsfelt Hansen, Michal Kouck, Pavel Pudlk, Emanuele Viola |
| 2011 | STOC | Exact algorithms for solving stochastic games: extended abstract. | Kristoffer Arnsfelt Hansen, Michal Kouck, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas |
| 2011 | STOC | Pseudorandom generators for group products: extended abstract. | Michal Kouck, Prajakta Nimbhorkar, Pavel Pudlk |
| 2009 | LICS | Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. | Kristoffer Arnsfelt Hansen, Michal Kouck, Peter Bro Miltersen |
| 2008 | ICALP | How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs). | Chen Avin, Michal Kouck, Zvi Lotker |
| 2008 | SPAA | Many random walks are faster than one. | Noga Alon, Chen Avin, Michal Kouck, Gady Kozma, Zvi Lotker, Mark R. Tuttle |
| 2007 | CiE | Circuit Complexity of Regular Languages. | Michal Kouck |
| 2007 | CSR | Inverting Onto Functions and Polynomial Hierarchy. | Harry Buhrman, Lance Fortnow, Michal Kouck, John D. Rogers, Nikolai K. Vereshchagin |
| 2007 | STACS | Languages with Bounded Multiparty Communication Complexity. | Arkadev Chattopadhyay, Andreas Krebs, Michal Kouck, Mario Szegedy, Pascal Tesson, Denis Thrien |
| 2006 | CSR | Incremental Branching Programs. | Anna Gl, Michal Kouck, Pierre McKenzie |
| 2005 | STOC | Bounded-depth circuits: separating wires from gates. | Michal Kouck, Pavel Pudlk, Denis Thrien |
| 2004 | STACS | What Can be Efficiently Reduced to the K-Random Strings? | Eric Allender, Harry Buhrman, Michal Kouck |
| 2002 | FOCS | Power from Random Strings. | Eric Allender, Harry Buhrman, Michal Kouck, Dieter van Melkebeek, Detlef Ronneburger |
| 2001 | COCOON | Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n | Michal Kouck |