Time-Space Tradeoffs in the Counting Hierarchy - Eric Allender; Michal Koucký 001; Detlef Ronneburger; Sambuddha Roy; V. Vinay (Electron. Colloquium Comput. Complex., 2001)

Universal traversal sequences with backtracking. - Michal Koucký 001 (J. Comput. Syst. Sci., 2002)

Derandomization and Distinguishing Complexity. - Eric Allender; Michal Koucký 001; Detlef Ronneburger; Sambuddha Roy (CCC, 2003)

Log-space constructible universal traversal sequences for cycles of length O(n4.03). - Michal Koucký 001 (Theor. Comput. Sci., 2003)

What Can be Efficiently Reduced to the K-Random Strings? - Eric Allender; Harry Buhrman; Michal Koucký 001 (STACS, 2004)

What Can be Efficiently Reduced to the Kolmogorov-Random Strings? - Eric Allender; Harry Buhrman; Michal Koucký 001 (Electron. Colloquium Comput. Complex., 2004)

Bounded-depth circuits: separating wires from gates. - Michal Koucký 001; Pavel Pudlák; Denis Thérien (STOC, 2005)

Incremental branching programs - Anna Gál; Michal Koucký 001; Pierre McKenzie (Electron. Colloquium Comput. Complex., 2005)

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games. - Michal Koucký 001; Clemens Lautemann; Sebastian Poloczek; Denis Thérien (CCC, 2006)

Inverting onto functions might not be hard. - Harry Buhrman; Lance Fortnow; Michal Koucký 001; John D. Rogers; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2006)

Languages with Bounded Multiparty Communication Complexity. - Arkadev Chattopadhyay; Michal Koucký 001; Andreas Krebs; Mario Szegedy; Pascal Tesson; Denis Thérien (Electron. Colloquium Comput. Complex., 2006)

Power from Random Strings. - Eric Allender; Harry Buhrman; Michal Koucký 001; Dieter van Melkebeek; Detlef Ronneburger (SIAM J. Comput., 2006)

Inverting Onto Functions and Polynomial Hierarchy. - Harry Buhrman; Lance Fortnow; Michal Koucký 001; John D. Rogers; Nikolai K. Vereshchagin (CSR, 2007)

Randomised Individual Communication Complexity. - Harry Buhrman; Michal Koucký 001; Nikolai K. Vereshchagin (CCC, 2008)

How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs). - Chen Avin; Michal Koucký 001; Zvi Lotker (ICALP (1), 2008)

Amplifying Lower Bounds by Means of Self-Reducibility. - Eric Allender; Michal Koucký 001 (Electron. Colloquium Comput. Complex., 2008)

Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. - Kristoffer Arnsfelt Hansen; Michal Koucký 001; Peter Bro Miltersen (LICS, 2009)

Circuit Complexity of Regular Languages. - Michal Koucký 001 (Theory Comput. Syst., 2009)

Derandomizing from Random Strings. - Harry Buhrman; Lance Fortnow; Michal Koucký 001; Bruno Loff (CCC, 2010)

A New Characterization of ACC0 and Probabilistic CC0. - Kristoffer Arnsfelt Hansen; Michal Koucký 001 (Comput. Complex., 2010)

Book review. - Michal Koucký 001 (Comput. Sci. Rev., 2010)

Pseudorandom Generators for Group Products. - Michal Koucký 001; Prajakta Nimbhorkar; Pavel Pudlák (Electron. Colloquium Comput. Complex., 2010)

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? - Harry Buhrman; Lance Fortnow; Michal Koucký 001; John D. Rogers; Nikolai K. Vereshchagin (Theory Comput. Syst., 2010)

Exact algorithms for solving stochastic games: extended abstract. - Kristoffer Arnsfelt Hansen; Michal Koucký 001; Niels Lauritzen; Peter Bro Miltersen; Elias P. Tsigaridas (STOC, 2011)

Pseudorandom generators for group products: extended abstract. - Michal Koucký 001; Prajakta Nimbhorkar; Pavel Pudlák (STOC, 2011)

Many Random Walks Are Faster Than One. - Noga Alon; Chen Avin; Michal Koucký 001; Gady Kozma; Zvi Lotker; Mark R. Tuttle (Comb. Probab. Comput., 2011)

Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). - Martin Grohe; Michal Koucký 001; Rüdiger Reischuk; Dieter van Melkebeek (Dagstuhl Reports, 2011)

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. - Anna Gál; Kristoffer Arnsfelt Hansen; Michal Koucký 001; Pavel Pudlák; Emanuele Viola (Electron. Colloquium Comput. Complex., 2011)

The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. - Eric Allender; Michal Koucký 001; Detlef Ronneburger; Sambuddha Roy (J. Comput. Syst. Sci., 2011)

On Online Labeling with Polynomially Many Labels. - Martin Babka; Jan Bulánek; Vladimír Cunát; Michal Koucký 001; Michael E. Saks (ESA, 2012)

Exact Algorithms for Solving Stochastic Games - Kristoffer Arnsfelt Hansen; Michal Koucký 001; Niels Lauritzen; Peter Bro Miltersen; Elias P. Tsigaridas (CoRR, 2012)

Towards a Reverse Newman's Theorem in Interactive Information Complexity. - Joshua Brody; Harry Buhrman; Michal Koucký 001; Bruno Loff; Florian Speelman (Electron. Colloquium Comput. Complex., 2012)

On Randomized Online Labeling with Polynomially Many Labels. - Jan Bulánek; Michal Koucký 001; Michael E. Saks (ICALP (1), 2013)

Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121). - Anna Gál; Michal Koucký 001; Oded Regev 001; Rüdiger Reischuk (Dagstuhl Reports, 2014)

Computing with a full memory: Catalytic space. - Harry Buhrman; Richard Cleve; Michal Koucký 001; Bruno Loff; Florian Speelman (Electron. Colloquium Comput. Complex., 2014)

Information Complexity for Multiparty Communication. - Diptarka Chakraborty; Elazar Goldenberg; Michal Koucký 001 (Electron. Colloquium Comput. Complex., 2014)

The Hardness of Being Private. - Anil Ada; Arkadev Chattopadhyay; Stephen A. Cook; Lila Fontes; Michal Koucký 001; Toniann Pitassi (ACM Trans. Comput. Theory, 2014)

A New Approach to the Sensitivity Conjecture. - Justin Gilmer; Michal Koucký 001; Michael E. Saks (ITCS, 2015)

Low Distortion Embedding from Edit to Hamming Distance using Coupling. - Diptarka Chakraborty; Elazar Goldenberg; Michal Koucký 001 (Electron. Colloquium Comput. Complex., 2015)

Nonuniform catalytic space and the direct sum for space. - Michal Koucký 001 (Electron. Colloquium Comput. Complex., 2015)

Tight Lower Bounds for the Online Labeling Problem. - Jan Bulánek; Michal Koucký 001; Michael E. Saks (SIAM J. Comput., 2015)

The Big Match in Small Space - (Extended Abstract). - Kristoffer Arnsfelt Hansen; Rasmus Ibsen-Jensen; Michal Koucký 001 (SAGT, 2016)

Streaming algorithms for embedding and computing edit distance in the low distance regime. - Diptarka Chakraborty; Elazar Goldenberg; Michal Koucký 001 (STOC, 2016)

Towards a Reverse Newman's Theorem in Interactive Information Complexity. - Joshua Brody; Harry Buhrman; Michal Koucký 001; Bruno Loff; Florian Speelman; Nikolai K. Vereshchagin (Algorithmica, 2016)

Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees. - Diptarka Chakraborty; Elazar Goldenberg; Michal Koucký 001 (CoRR, 2016)

The Big Match in Small Space. - Kristoffer Arnsfelt Hansen; Rasmus Ibsen-Jensen; Michal Koucký 001 (CoRR, 2016)

Catalytic computation. - Michal Koucký 001 (Bull. EATCS, 2016)

Expander Construction in VNC1. - Sam Buss; Valentine Kabanets; Antonina Kolokolova; Michal Koucký 001 (Electron. Colloquium Comput. Complex., 2016)

Lower Bounds for Elimination via Weak Regularity. - Arkadev Chattopadhyay; Pavel Dvorák; Michal Koucký 001; Bruno Loff; Sagnik Mukhopadhyay (Electron. Colloquium Comput. Complex., 2016)

Expander Construction in VNC1. - Sam Buss; Valentine Kabanets; Antonina Kolokolova; Michal Koucký 001 (ITCS, 2017)

Simulation Theorems via Pseudorandom Properties. - Arkadev Chattopadhyay; Michal Koucký 001; Bruno Loff; Sagnik Mukhopadhyay (CoRR, 2017)

Optimal Quasi-Gray Codes: Does the Alphabet Matter? - Diptarka Chakraborty; Debarati Das 001; Michal Koucký 001; Nitin Saurabh (CoRR, 2017)

Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). - Anna Gál; Michal Koucký 001; Oded Regev 001; Till Tantau (Dagstuhl Reports, 2017)

Composition and Simulation Theorems via Pseudo-random Properties. - Arkadev Chattopadhyay; Michal Koucký 001; Bruno Loff; Sagnik Mukhopadhyay (Electron. Colloquium Comput. Complex., 2017)

Simulation Beats Richness: New Data-Structure Lower Bounds. - Arkadev Chattopadhyay; Michal Koucký 001; Bruno Loff; Sagnik Mukhopadhyay (Electron. Colloquium Comput. Complex., 2017)

A Communication Game Related to the Sensitivity Conjecture. - Justin Gilmer; Michal Koucký 001; Michael E. Saks (Theory Comput., 2017)

Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. - Diptarka Chakraborty; Debarati Das 001; Michal Koucký 001; Nitin Saurabh (ESA, 2018)

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. - Debarati Das 001; Michal Koucký 001; Michael E. Saks (STACS, 2018)

Approximate Online Pattern Matching in Sub-linear Time. - Diptarka Chakraborty; Debarati Das 001; Michal Koucký 001 (CoRR, 2018)

Improved bounds on Fourier entropy and Min-entropy. - Srinivasan Arunachalam; Sourav Chakraborty 001; Michal Koucký 001; Nitin Saurabh; Ronald de Wolf (Electron. Colloquium Comput. Complex., 2018)

Catalytic Space: Non-determinism and Hierarchy. - Harry Buhrman; Michal Koucký 001; Bruno Loff; Florian Speelman (Theory Comput. Syst., 2018)

Cover time and mixing time of random walks on dynamic graphs. - Chen Avin; Michal Koucký 001; Zvi Lotker (Random Struct. Algorithms, 2018)

Approximate Online Pattern Matching in Sublinear Time. - Diptarka Chakraborty; Debarati Das 001; Michal Koucký 001 (FSTTCS, 2019)

Stronger Lower Bounds for Online ORAM. - Pavel Hubácek; Michal Koucký 001; Karel Král 002; Veronika Slívová (TCC (2), 2019)

Simulation Theorems via Pseudo-random Properties. - Arkadev Chattopadhyay; Michal Koucký 001; Bruno Loff; Sagnik Mukhopadhyay (Comput. Complex., 2019)

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. - Michal Koucký 001; Vojtech Rödl; Navid Talebanfard (Electron. Colloquium Comput. Complex., 2019)

On Online Labeling with Large Label Set. - Martin Babka; Jan Bulánek; Vladimír Cunát; Michal Koucký 001; Michael E. Saks (SIAM J. Discret. Math., 2019)

Constant factor approximations to edit distance on far input pairs in nearly linear time. - Michal Koucký 001; Michael E. Saks (STOC, 2020)

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time. - Diptarka Chakraborty; Debarati Das 001; Elazar Goldenberg; Michal Koucký 001; Michael E. Saks (J. ACM, 2020)

Circuit complexity of regular languages. - Michal Koucký 001 (Handbook of Automata Theory (I.), 2021)

Computing Edit Distance (Invited Talk). - Michal Koucký 001 (CPM, 2021)

Data Structures Lower Bounds and Popular Conjectures. - Pavel Dvorák; Michal Koucký 001; Karel Král 002; Veronika Slívová (ESA, 2021)

Sorting Short Integers. - Michal Koucký 001; Karel Král 002 (ICALP, 2021)

Barrington Plays Cards: The Complexity of Card-Based Protocols. - Pavel Dvorák; Michal Koucký 001 (STACS, 2021)

High Entropy Random Selection Protocols. - Harry Buhrman; Matthias Christandl; Michal Koucký 001; Zvi Lotker; Boaz Patt-Shamir; Nikolai K. Vereshchagin (Algorithmica, 2021)

Sorting Short Integers: The Exposition. - Michal Koucký 001 (Bull. EATCS, 2021)

Streaming k-Edit Approximate Pattern Matching via String Decomposition. - Sudatta Bhattacharya; Michal Koucký 001 (ICALP, 2023)

Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. - Michal Koucký 001; Michael E. Saks (SODA, 2023)

Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching. - Sudatta Bhattacharya; Michal Koucký 001 (STOC, 2023)

Automata and Formal Languages: Shall we let them go? - Michal Koucký 001 (Bull. EATCS, 2023)

Nearly Optimal List Labeling. - Michael A. Bender; Alex Conway 001; Martín Farach-Colton; Hanna Komlós; Michal Koucký 001; William Kuszmaul; Michael E. Saks (FOCS, 2024)

Many Flavors of Edit Distance. - Sudatta Bhattacharya; Sanjana Dey; Elazar Goldenberg; Michal Koucký 001 (FSTTCS, 2024)

Almost Linear Size Edit Distance Sketch. - Michal Koucký 001; Michael E. Saks (STOC, 2024)

SquareSort: a cache-oblivious sorting algorithm. - Michal Koucký 001; Josef Matejka (CoRR, 2024)

Collapsing Catalytic Classes. - Michal Koucký 001; Ian Mertz; Edward Pyne; Sasha Sami (Electron. Colloquium Comput. Complex., 2025)

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric. - Sudatta Bhattacharya; Sanjana Dey; Elazar Goldenberg; Mursalin Habib; Bernhard Haeupler; Karthik C. S. 001; Michal Koucký 001 (CoRR, 2025)