Professional Interests

Project EPAC: Efficient approximation algorithms and circuit complexity

Project LBCAD: Lower bounds for combinatorial algorithms and dynamic problems

On-line Publications

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

On-line Manuscripts, Technical Reports and Thesis

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

On-line presentations