default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMichal Koucký 0001
Person information
- affiliation: Charles University, Computer Science Institute, Prague, Czech Republic
- affiliation: Academy of Sciences of Czech Republic, Institute of Mathematics, Prague, Czech Republic
- affiliation (former): McGill University, Montréal, Canada
Other persons with the same name
- Michal Koucký 0002
![[0000-0003-2807-7635]](https://dblp.dagstuhl.de/img/orcid-mark.12x12.png "0000-0003-2807-7635")
— Charles University, Obstetrics and Gynaecology Clinic, Prague, Czech Republic
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c53]Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael E. Saks:
Nearly Optimal List Labeling. FOCS 2024: 2253-2274- [c52]Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Michal Koucký:
Many Flavors of Edit Distance. FSTTCS 2024: 11:1-11:16 - [c51]Michal Koucký, Michael E. Saks:
Almost Linear Size Edit Distance Sketch. STOC 2024: 956-967 - [i52]Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael E. Saks:
Nearly Optimal List Labeling. CoRR abs/2405.00807 (2024) - [i51]Michal Koucký, Michael Saks:
Almost Linear Size Edit Distance Sketch. CoRR abs/2406.11225 (2024) - [i50]Michal Koucký, Josef Matejka:
SquareSort: a cache-oblivious sorting algorithm. CoRR abs/2407.14801 (2024) - [i49]Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Michal Koucký:
Many Flavors of Edit Distance. CoRR abs/2410.09877 (2024) - 2023
- [j29]Michal Koucký:
Automata and Formal Languages: Shall we let them go? Bull. EATCS 140 (2023) - [c50]Sudatta Bhattacharya, Michal Koucký:
Streaming k-Edit Approximate Pattern Matching via String Decomposition. ICALP 2023: 22:1-22:14 - [c49]Michal Koucký, Michael E. Saks:
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. SODA 2023: 5203-5219 - [c48]Sudatta Bhattacharya, Michal Koucký:
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching. STOC 2023: 219-232 - [i48]Sudatta Bhattacharya, Michal Koucký:
Locally consistent decomposition of strings with applications to edit distance sketching. CoRR abs/2302.04475 (2023) - [i47]Sudatta Bhattacharya, Michal Koucký:
Streaming k-edit approximate pattern matching via string decomposition. CoRR abs/2305.00615 (2023) - 2021
- [j28]Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin:
High Entropy Random Selection Protocols. Algorithmica 83(2): 667-694 (2021) - [j27]Michal Koucký:
Sorting Short Integers: The Exposition. Bull. EATCS 135 (2021) - [j26]Michal Koucký, Vojtech Rödl, Navid Talebanfard:
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. Log. Methods Comput. Sci. 17(4) (2021) - [j25]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): 22:1-22:40 (2021) - [c47]Michal Koucký:
Computing Edit Distance (Invited Talk). CPM 2021: 2:1-2:1 - [c46]Pavel Dvorák, Michal Koucký, Karel Král, Veronika Slívová:
Data Structures Lower Bounds and Popular Conjectures. ESA 2021: 39:1-39:15 - [c45]Michal Koucký, Karel Král:
Sorting Short Integers. ICALP 2021: 88:1-88:17 - [c44]Pavel Dvorák, Michal Koucký:
Barrington Plays Cards: The Complexity of Card-Based Protocols. STACS 2021: 26:1-26:17 - [p1]Michal Koucký:
Circuit complexity of regular languages. Handbook of Automata Theory (I.) 2021: 493-523 - [i46]Pavel Dvorák, Michal Koucký, Karel Král, Veronika Slívová:
Data Structures Lower Bounds and Popular Conjectures. CoRR abs/2102.09294 (2021) - [i45]Michal Koucký, Karel Král:
Sorting Short Integers. CoRR abs/2102.10027 (2021) - [i44]Michal Koucký, Vojtech Rödl, Navid Talebanfard:
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. CoRR abs/2105.06744 (2021) - 2020
- [j24]Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký:
Expander construction in VNC1. Ann. Pure Appl. Log. 171(7): 102796 (2020) - [j23]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): 36:1-36:22 (2020) - [c43]Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf:
Improved Bounds on Fourier Entropy and Min-Entropy. STACS 2020: 45:1-45:19 - [c42]Michal Koucký, Michael E. Saks:
Constant factor approximations to edit distance on far input pairs in nearly linear time. STOC 2020: 699-712 - [i43]Pavel Dvorák, Michal Koucký:
Barrington Plays Cards: The Complexity of Card-based Protocols. CoRR abs/2010.08445 (2020)
2010 – 2019
- 2019
- [j22]Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Simulation Theorems via Pseudo-random Properties. Comput. Complex. 28(4): 617-659 (2019) - [j21]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): 1175-1193 (2019) - [c41]Diptarka Chakraborty, Debarati Das, Michal Koucký:
Approximate Online Pattern Matching in Sublinear Time. FSTTCS 2019: 10:1-10:15 - [c40]Pavel Hubácek, Michal Koucký, Karel Král, Veronika Slívová:
Stronger Lower Bounds for Online ORAM. TCC (2) 2019: 264-284 - [i42]Pavel Hubácek, Michal Koucký, Karel Král, Veronika Slívová:
Stronger Lower Bounds for Online ORAM. CoRR abs/1903.03385 (2019) - [i41]Michal Koucký, Michael E. Saks:
Constant factor approximations to edit distance on far input pairs in nearly linear time. CoRR abs/1904.05459 (2019) - [i40]Michal Koucký, Vojtech Rödl, Navid Talebanfard:
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j20]Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman:
Catalytic Space: Non-determinism and Hierarchy. Theory Comput. Syst. 62(1): 116-135 (2018) - [j19]Chen Avin, Michal Koucký, Zvi Lotker:
Cover time and mixing time of random walks on dynamic graphs. Random Struct. Algorithms 52(4): 576-596 (2018) - [c39]Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh:
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. ESA 2018: 12:1-12:15 - [c38]Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks:
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS 2018: 979-990 - [c37]Debarati Das, Michal Koucký, Michael E. Saks:
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. STACS 2018: 23:1-23:14 - [c36]Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Simulation beats richness: new data-structure lower bounds. STOC 2018: 1013-1020 - [i39]Debarati Das, Michal Koucký, Michael E. Saks:
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. CoRR abs/1801.05202 (2018) - [i38]Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf:
Improved bounds on Fourier entropy and Min-entropy. CoRR abs/1809.09819 (2018) - [i37]Diptarka Chakraborty, Debarati Das, Michal Koucký:
Approximate Online Pattern Matching in Sub-linear Time. CoRR abs/1810.03551 (2018) - [i36]Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks:
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR abs/1810.03664 (2018) - [i35]Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf:
Improved bounds on Fourier entropy and Min-entropy. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j18]Justin Gilmer, Michal Koucký, Michael E. Saks:
A Communication Game Related to the Sensitivity Conjecture. Theory Comput. 13(1): 1-18 (2017) - [c35]Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký:
Expander Construction in VNC1. ITCS 2017: 31:1-31:26 - [c34]Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Lower Bounds for Elimination via Weak Regularity. STACS 2017: 21:1-21:14 - [i34]Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Simulation Theorems via Pseudorandom Properties. CoRR abs/1704.06807 (2017) - [i33]Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh:
Optimal Quasi-Gray Codes: Does the Alphabet Matter? CoRR abs/1712.01834 (2017) - [i32]Anna Gál, Michal Koucký, Oded Regev, Till Tantau:
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). Dagstuhl Reports 7(3): 45-69 (2017) - [i31]Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Composition and Simulation Theorems via Pseudo-random Properties. Electron. Colloquium Comput. Complex. TR17 (2017) - [i30]Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Simulation Beats Richness: New Data-Structure Lower Bounds. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j17]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): 749-781 (2016) - [j16]Michal Koucký:
Catalytic computation. Bull. EATCS 118 (2016) - [c33]Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Michal Koucký:
The Big Match in Small Space - (Extended Abstract). SAGT 2016: 64-76 - [c32]Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman:
Catalytic Space: Non-determinism and Hierarchy. STACS 2016: 24:1-24:13 - [c31]Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký:
Streaming algorithms for embedding and computing edit distance in the low distance regime. STOC 2016: 712-725 - [i29]Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Michal Koucký:
The Big Match in Small Space. CoRR abs/1604.07634 (2016) - [i28]Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký:
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees. CoRR abs/1607.03718 (2016) - [i27]Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký:
Expander Construction in VNC1. Electron. Colloquium Comput. Complex. TR16 (2016) - [i26]Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Lower Bounds for Elimination via Weak Regularity. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j15]Jan Bulánek, Michal Koucký, Michael E. Saks:
Tight Lower Bounds for the Online Labeling Problem. SIAM J. Comput. 44(6): 1765-1797 (2015) - [c30]Justin Gilmer, Michal Koucký, Michael E. Saks:
A New Approach to the Sensitivity Conjecture. ITCS 2015: 247-254 - [i25]Justin Gilmer, Michal Koucký, Michael E. Saks:
A communication game related to the sensitivity conjecture. CoRR abs/1511.07729 (2015) - [i24]Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký:
Low Distortion Embedding from Edit to Hamming Distance using Coupling. Electron. Colloquium Comput. Complex. TR15 (2015) - [i23]Michal Koucký:
Nonuniform catalytic space and the direct sum for space. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j14]Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi:
The Hardness of Being Private. ACM Trans. Comput. Theory 6(1): 1:1-1:24 (2014) - [c29]Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman:
Computing with a full memory: catalytic space. STOC 2014: 857-866 - [i22]Anna Gál, Michal Koucký, Oded Regev, Rüdiger Reischuk:
Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121). Dagstuhl Reports 4(3): 62-84 (2014) - [i21]Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman:
Computing with a full memory: Catalytic space. Electron. Colloquium Comput. Complex. TR14 (2014) - [i20]Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký:
Information Complexity for Multiparty Communication. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j13]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): 6611-6627 (2013) - [c28]Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. CCC 2013: 24-33 - [c27]Jan Bulánek, Michal Koucký, Michael E. Saks:
On Randomized Online Labeling with Polynomially Many Labels. ICALP (1) 2013: 291-302 - 2012
- [c26]Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi:
The Hardness of Being Private. CCC 2012: 192-202 - [c25]Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks:
On Online Labeling with Polynomially Many Labels. ESA 2012: 121-132 - [c24]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: 479-494 - [c23]Jan Bulánek, Michal Koucký, Michael E. Saks:
Tight lower bounds for the online labeling problem. STOC 2012: 1185-1198 - [i19]Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas:
Exact Algorithms for Solving Stochastic Games. CoRR abs/1202.3898 (2012) - [i18]Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks:
On Online Labeling with Polynomially Many Labels. CoRR abs/1210.3197 (2012) - [i17]Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j12]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): 481-502 (2011) - [j11]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): 14-40 (2011) - [c22]Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas:
Exact algorithms for solving stochastic games: extended abstract. STOC 2011: 205-214 - [c21]Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák:
Pseudorandom generators for group products: extended abstract. STOC 2011: 263-272 - [i16]Jan Bulánek, Michal Koucký, Michael E. Saks:
Tight lower bounds for online labeling problem. CoRR abs/1112.5636 (2011) - [i15]Martin Grohe, Michal Koucký, Rüdiger Reischuk, Dieter van Melkebeek:
Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). Dagstuhl Reports 1(3): 42-66 (2011) - [i14]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. TR11 (2011) - 2010
- [j10]Kristoffer Arnsfelt Hansen, Michal Koucký:
A New Characterization of ACC0 and Probabilistic CC0. Comput. Complex. 19(2): 211-234 (2010) - [j9]Michal Koucký:
Book review. Comput. Sci. Rev. 4(1): 61-63 (2010) - [j8]Eric Allender, Michal Koucký:
Amplifying lower bounds by means of self-reducibility. J. ACM 57(3): 14:1-14:36 (2010) - [j7]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): 143-156 (2010) - [c20]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff:
Derandomizing from Random Strings. CCC 2010: 58-63 - [i13]Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák:
Pseudorandom Generators for Group Products. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j6]Michal Koucký:
Circuit Complexity of Regular Languages. Theory Comput. Syst. 45(4): 865-879 (2009) - [c19]Kristoffer Arnsfelt Hansen, Michal Koucký:
A New Characterization of ACC0 and Probabilistic CC0. CCC 2009: 27-34 - [c18]Kristoffer Arnsfelt Hansen, Michal Koucký, Peter Bro Miltersen:
Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. LICS 2009: 332-341 - [i12]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff:
Derandomizing from Random Strings. CoRR abs/0912.3162 (2009) - [i11]Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy:
The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j5]Anna Gál, Michal Koucký, Pierre McKenzie:
Incremental Branching Programs. Theory Comput. Syst. 43(2): 159-184 (2008) - [c17]Eric Allender, Michal Koucký:
Amplifying Lower Bounds by Means of Self-Reducibility. CCC 2008: 31-40 - [c16]Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin:
Randomised Individual Communication Complexity. CCC 2008: 321-331 - [c15]Chen Avin, Michal Koucký, Zvi Lotker:
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs). ICALP (1) 2008: 121-132 - [c14]Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, Mark R. Tuttle:
Many random walks are faster than one. SPAA 2008: 119-128 - [i10]Eric Allender, Michal Koucký:
Amplifying Lower Bounds by Means of Self-Reducibility. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [c13]Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin:
High Entropy Random Selection Protocols. APPROX-RANDOM 2007: 366-379 - [c12]Michal Koucký:
Circuit Complexity of Regular Languages. CiE 2007: 426-435 - [c11]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103 - [c10]Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien:
Languages with Bounded Multiparty Communication Complexity. STACS 2007: 500-511 - [i9]Nikolai K. Vereshchagin, Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir:
High Entropy Random Selection Protocols. Algebraic Methods in Computational Complexity 2007 - 2006
- [j4]Eric Allender, Harry Buhrman, Michal Koucký:
What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Log. 138(1-3): 2-19 (2006) - [j3]Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger:
Power from Random Strings. SIAM J. Comput. 35(6): 1467-1493 (2006) - [c9]Michal Koucký, Clemens Lautemann, Sebastian Poloczek, Denis Thérien:
Circuit Lower Bounds via Ehrenfeucht-Fraisse Games. CCC 2006: 190-201 - [c8]Anna Gál, Michal Koucký, Pierre McKenzie:
Incremental Branching Programs. CSR 2006: 178-190 - [i8]Anna Gál, Pierre McKenzie, Michal Koucký:
Incremental branching programs. Complexity of Boolean Functions 2006 - [i7]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. TR06 (2006) - [i6]