Michal Koucký

ORCID

Publication Activity (10 Years)

Years Active: 2001-2024
Publications (10 Years): 65

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

STOC

STACS

Publications

Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael E. Saks
Nearly Optimal List Labeling. CoRR (2024)
Michal Koucký, Michael Saks
Almost Linear Size Edit Distance Sketch. CoRR (2024)
Michal Koucký, Michael E. Saks
Almost Linear Size Edit Distance Sketch. STOC (2024)
Sudatta Bhattacharya, Michal Koucký
Streaming k-Edit Approximate Pattern Matching via String Decomposition. ICALP (2023)
Sudatta Bhattacharya, Michal Koucký
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching. STOC (2023)
Michal Koucký
Automata and Formal Languages: Shall we let them go? Bull. EATCS 140 (2023)
Sudatta Bhattacharya, Michal Koucký
Locally consistent decomposition of strings with applications to edit distance sketching. CoRR (2023)
Michal Koucký, Michael E. Saks
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. SODA (2023)
Sudatta Bhattacharya, Michal Koucký
Streaming k-edit approximate pattern matching via string decomposition. CoRR (2023)
Michal Koucký, Vojtech Rödl, Navid Talebanfard
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. CoRR (2021)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved Bounds on Fourier Entropy and Min-entropy. ACM Trans. Comput. Theory 13 (4) (2021)
Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
High Entropy Random Selection Protocols. Algorithmica 83 (2) (2021)
Michal Koucký, Karel Král
Sorting Short Integers. CoRR (2021)
Michal Koucký
Sorting Short Integers: The Exposition. Bull. EATCS 135 (2021)
Michal Koucký, Karel Král
Sorting Short Integers. ICALP (2021)
Pavel Dvorák, Michal Koucký, Karel Král, Veronika Slívová
Data Structures Lower Bounds and Popular Conjectures. ESA (2021)
Pavel Dvorák, Michal Koucký
Barrington Plays Cards: The Complexity of Card-Based Protocols. STACS (2021)
Michal Koucký
Computing Edit Distance (Invited Talk). CPM (2021)
Pavel Dvorák, Michal Koucký, Karel Král, Veronika Slívová
Data Structures Lower Bounds and Popular Conjectures. CoRR (2021)
Michal Koucký, Vojtech Rödl, Navid Talebanfard
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. Log. Methods Comput. Sci. 17 (4) (2021)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
. Ann. Pure Appl. Log. 171 (7) (2020)
Michal Koucký, Michael E. Saks
Constant factor approximations to edit distance on far input pairs in nearly linear time. STOC (2020)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved Bounds on Fourier Entropy and Min-Entropy. STACS (2020)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time. J. ACM 67 (6) (2020)
Pavel Dvorák, Michal Koucký
Barrington Plays Cards: The Complexity of Card-based Protocols. CoRR (2020)
Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks
On Online Labeling with Large Label Set. SIAM J. Discret. Math. 33 (3) (2019)
Diptarka Chakraborty, Debarati Das, Michal Koucký
Approximate Online Pattern Matching in Sublinear Time. FSTTCS (2019)
Pavel Hubácek, Michal Koucký, Karel Král, Veronika Slívová
Stronger Lower Bounds for Online ORAM. TCC (2) (2019)
Michal Koucký, Vojtech Rödl, Navid Talebanfard
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. Electron. Colloquium Comput. Complex. 26 (2019)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation Theorems via Pseudo-random Properties. Comput. Complex. 28 (4) (2019)
Michal Koucký, Michael E. Saks
Constant factor approximations to edit distance on far input pairs in nearly linear time. CoRR (2019)
Pavel Hubácek, Michal Koucký, Karel Král, Veronika Slívová
Stronger Lower Bounds for Online ORAM. CoRR (2019)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS (2018)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation beats richness: new data-structure lower bounds. STOC (2018)
Diptarka Chakraborty, Debarati Das, Michal Koucký
Approximate Online Pattern Matching in Sub-linear Time. CoRR (2018)
Debarati Das, Michal Koucký, Michael E. Saks
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. CoRR (2018)
Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. ESA (2018)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR (2018)
Chen Avin, Michal Koucký, Zvi Lotker
Cover time and mixing time of random walks on dynamic graphs. Random Struct. Algorithms 52 (4) (2018)
Debarati Das, Michal Koucký, Michael E. Saks
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. STACS (2018)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved bounds on Fourier entropy and Min-entropy. CoRR (2018)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved bounds on Fourier entropy and Min-entropy. Electron. Colloquium Comput. Complex. 25 (2018)
Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
Catalytic Space: Non-determinism and Hierarchy. Theory Comput. Syst. 62 (1) (2018)
Anna Gál, Michal Koucký, Oded Regev, Till Tantau
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). Dagstuhl Reports 7 (3) (2017)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Composition and Simulation Theorems via Pseudo-random Properties. Electron. Colloquium Comput. Complex. 24 (2017)
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Lower Bounds for Elimination via Weak Regularity. STACS (2017)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation Theorems via Pseudorandom Properties. CoRR (2017)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation Beats Richness: New Data-Structure Lower Bounds. Electron. Colloquium Comput. Complex. 24 (2017)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
Expander Construction in VNC1. ITCS (2017)
Justin Gilmer, Michal Koucký, Michael E. Saks
A Communication Game Related to the Sensitivity Conjecture. Theory Comput. 13 (1) (2017)
Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh
Optimal Quasi-Gray Codes: Does the Alphabet Matter? CoRR (2017)
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Michal Koucký
The Big Match in Small Space - (Extended Abstract). SAGT (2016)
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Michal Koucký
The Big Match in Small Space. CoRR (2016)
Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
Catalytic Space: Non-determinism and Hierarchy. STACS (2016)
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Lower Bounds for Elimination via Weak Regularity. Electron. Colloquium Comput. Complex. 23 (2016)
Michal Koucký
Catalytic computation. Bull. EATCS 118 (2016)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Streaming algorithms for embedding and computing edit distance in the low distance regime. STOC (2016)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolai K. Vereshchagin
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Algorithmica 76 (3) (2016)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
. Electron. Colloquium Comput. Complex. 23 (2016)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees. CoRR (2016)
Justin Gilmer, Michal Koucký, Michael E. Saks
A New Approach to the Sensitivity Conjecture. ITCS (2015)
Jan Bulánek, Michal Koucký, Michael E. Saks
Tight Lower Bounds for the Online Labeling Problem. SIAM J. Comput. 44 (6) (2015)
Michal Koucký
Nonuniform catalytic space and the direct sum for space. Electron. Colloquium Comput. Complex. 22 (2015)
Justin Gilmer, Michal Koucký, Michael E. Saks
A communication game related to the sensitivity conjecture. CoRR (2015)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Low Distortion Embedding from Edit to Hamming Distance using Coupling. Electron. Colloquium Comput. Complex. 22 (2015)
Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
The Hardness of Being Private. ACM Trans. Comput. Theory 6 (1) (2014)
Anna Gál, Michal Koucký, Oded Regev, Rüdiger Reischuk
Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121). Dagstuhl Reports 4 (3) (2014)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Information Complexity for Multiparty Communication. Electron. Colloquium Comput. Complex. 21 (2014)
Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
Computing with a full memory: Catalytic space. Electron. Colloquium Comput. Complex. 21 (2014)
Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
Computing with a full memory: catalytic space. STOC (2014)
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates. IEEE Trans. Inf. Theory 59 (10) (2013)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Computational Complexity Conference (2013)
Jan Bulánek, Michal Koucký, Michael E. Saks
On Randomized Online Labeling with Polynomially Many Labels. ICALP (1) (2013)
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. STOC (2012)
Jan Bulánek, Michal Koucký, Michael E. Saks
Tight lower bounds for the online labeling problem. STOC (2012)
Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks
On Online Labeling with Polynomially Many Labels. ESA (2012)
Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks
On Online Labeling with Polynomially Many Labels CoRR (2012)
Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
The Hardness of Being Private. Computational Complexity Conference (2012)
Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas
Exact Algorithms for Solving Stochastic Games CoRR (2012)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Electron. Colloquium Comput. Complex. 19 (2012)
Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, Mark R. Tuttle
Many Random Walks Are Faster Than One. Comb. Probab. Comput. 20 (4) (2011)
Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák
Pseudorandom generators for group products: extended abstract. STOC (2011)
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. Electron. Colloquium Comput. Complex. 18 (2011)
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci. 77 (1) (2011)
Jan Bulánek, Michal Koucký, Michael E. Saks
Tight lower bounds for online labeling problem CoRR (2011)
Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas
Exact algorithms for solving stochastic games: extended abstract. STOC (2011)
Martin Grohe, Michal Koucký, Rüdiger Reischuk, Dieter van Melkebeek
Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). Dagstuhl Reports 1 (3) (2011)
Kristoffer Arnsfelt Hansen, Michal Koucký
. Comput. Complex. 19 (2) (2010)
Eric Allender, Michal Koucký
Amplifying lower bounds by means of self-reducibility. J. ACM 57 (3) (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. 46 (1) (2010)
Michal Koucký
Book review. Comput. Sci. Rev. 4 (1) (2010)
Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák
Pseudorandom Generators for Group Products. Electron. Colloquium Comput. Complex. 17 (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
Derandomizing from Random Strings. Computational Complexity Conference (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
Derandomizing from Random Strings CoRR (2009)
Michal Koucký
Circuit Complexity of Regular Languages. Theory Comput. Syst. 45 (4) (2009)
Kristoffer Arnsfelt Hansen, Michal Koucký
. Computational Complexity Conference (2009)
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy
The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory. Electron. Colloquium Comput. Complex. 16 (2009)
Kristoffer Arnsfelt Hansen, Michal Koucký, Peter Bro Miltersen
Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. LICS (2009)
Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, Mark R. Tuttle
Many random walks are faster than one. SPAA (2008)
Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin
Randomised Individual Communication Complexity. Computational Complexity Conference (2008)

Michal Koucký.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Michal Koucký