Michal Koucký

Orcid: 0000-0003-0808-2269

Affiliations:
  • Charles University, Department of Mathematics, Prague, Czech Republic
  • Academy of Sciences of Czech Republic, Institute of Mathematics, Prague, Czech Republic
  • McGill University, Montréal, Canada (former)


According to our database1, Michal Koucký authored at least 81 papers between 2001 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Nearly Optimal List Labeling.
CoRR, 2024

2023
Automata and Formal Languages: Shall we let them go?
Bull. EATCS, 2023

Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Streaming k-Edit Approximate Pattern Matching via String Decomposition.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2021
Sorting Short Integers: The Exposition.
Bull. EATCS, 2021

High Entropy Random Selection Protocols.
Algorithmica, 2021

Barrington Plays Cards: The Complexity of Card-Based Protocols.
Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Sorting Short Integers.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Data Structures Lower Bounds and Popular Conjectures.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Computing Edit Distance (Invited Talk).
Proceedings of the 32nd Annual Symposium on Combinatorial Pattern Matching, 2021

Circuit complexity of regular languages.
Proceedings of the Handbook of Automata Theory., 2021

2020
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time.
J. ACM, 2020

Constant factor approximations to edit distance on far input pairs in nearly linear time.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019
On Online Labeling with Large Label Set.
SIAM J. Discret. Math., 2019

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm.
Electron. Colloquium Comput. Complex., 2019

Simulation Theorems via Pseudo-random Properties.
Comput. Complex., 2019

Stronger Lower Bounds for Online ORAM.
Proceedings of the Theory of Cryptography - 17th International Conference, 2019

Approximate Online Pattern Matching in Sublinear Time.
Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2018
Cover time and mixing time of random walks on dynamic graphs.
Random Struct. Algorithms, 2018

Catalytic Space: Non-determinism and Hierarchy.
Theory Comput. Syst., 2018

Improved bounds on Fourier entropy and Min-entropy.
Electron. Colloquium Comput. Complex., 2018

Approximate Online Pattern Matching in Sub-linear Time.
CoRR, 2018

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017
A Communication Game Related to the Sensitivity Conjecture.
Theory Comput., 2017

Simulation Beats Richness: New Data-Structure Lower Bounds.
Electron. Colloquium Comput. Complex., 2017

Composition and Simulation Theorems via Pseudo-random Properties.
Electron. Colloquium Comput. Complex., 2017

Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).
Dagstuhl Reports, 2017

Optimal Quasi-Gray Codes: Does the Alphabet Matter?
CoRR, 2017

Simulation Theorems via Pseudorandom Properties.
CoRR, 2017

Expander Construction in VNC1.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016
Lower Bounds for Elimination via Weak Regularity.
Electron. Colloquium Comput. Complex., 2016

Expander Construction in VNC<sup>1</sup>.
Electron. Colloquium Comput. Complex., 2016

Catalytic computation.
Bull. EATCS, 2016

The Big Match in Small Space.
CoRR, 2016

Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees.
CoRR, 2016

Towards a Reverse Newman's Theorem in Interactive Information Complexity.
Algorithmica, 2016

Streaming algorithms for embedding and computing edit distance in the low distance regime.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

The Big Match in Small Space - (Extended Abstract).
Proceedings of the Algorithmic Game Theory - 9th International Symposium, 2016

2015
Tight Lower Bounds for the Online Labeling Problem.
SIAM J. Comput., 2015

Nonuniform catalytic space and the direct sum for space.
Electron. Colloquium Comput. Complex., 2015

Low Distortion Embedding from Edit to Hamming Distance using Coupling.
Electron. Colloquium Comput. Complex., 2015

A New Approach to the Sensitivity Conjecture.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014
The Hardness of Being Private.
ACM Trans. Comput. Theory, 2014

Information Complexity for Multiparty Communication.
Electron. Colloquium Comput. Complex., 2014

Computing with a full memory: Catalytic space.
Electron. Colloquium Comput. Complex., 2014

Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121).
Dagstuhl Reports, 2014

2013
On Randomized Online Labeling with Polynomially Many Labels.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012
Towards a Reverse Newman's Theorem in Interactive Information Complexity.
Electron. Colloquium Comput. Complex., 2012

Exact Algorithms for Solving Stochastic Games
CoRR, 2012

On Online Labeling with Polynomially Many Labels.
Proceedings of the Algorithms - ESA 2012, 2012

2011
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.
J. Comput. Syst. Sci., 2011

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.
Electron. Colloquium Comput. Complex., 2011

Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121).
Dagstuhl Reports, 2011

Many Random Walks Are Faster Than One.
Comb. Probab. Comput., 2011

Pseudorandom generators for group products: extended abstract.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Exact algorithms for solving stochastic games: extended abstract.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?
Theory Comput. Syst., 2010

Amplifying lower bounds by means of self-reducibility.
J. ACM, 2010

Pseudorandom Generators for Group Products.
Electron. Colloquium Comput. Complex., 2010

Book review.
Comput. Sci. Rev., 2010

A New Characterization of ACC<sup>0</sup> and Probabilistic CC<sup>0</sup>.
Comput. Complex., 2010

Derandomizing from Random Strings.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009
Circuit Complexity of Regular Languages.
Theory Comput. Syst., 2009

Winning Concurrent Reachability Games Requires Doubly-Exponential Patience.
Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

2008
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs).
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Randomised Individual Communication Complexity.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007
Inverting Onto Functions and Polynomial Hierarchy.
Proceedings of the Computer Science, 2007

2006
Languages with Bounded Multiparty Communication Complexity.
Electron. Colloquium Comput. Complex., 2006

Inverting onto functions might not be hard.
Electron. Colloquium Comput. Complex., 2006

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005
Incremental branching programs
Electron. Colloquium Comput. Complex., 2005

Bounded-depth circuits: separating wires from gates.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004
What Can be Efficiently Reduced to the Kolmogorov-Random Strings?
Electron. Colloquium Comput. Complex., 2004

What Can be Efficiently Reduced to the K-Random Strings?
Proceedings of the STACS 2004, 2004

2003
Log-space constructible universal traversal sequences for cycles of length O(n<sup>4.03</sup>).
Theor. Comput. Sci., 2003

Derandomization and Distinguishing Complexity.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
Universal traversal sequences with backtracking.
J. Comput. Syst. Sci., 2002

Power from Random Strings
Electron. Colloquium Comput. Complex., 2002

2001
Time-Space Tradeoffs in the Counting Hierarchy
Electron. Colloquium Comput. Complex., 2001


  Loading...