Michal Koucký

Josef Matejka

CoRR, 2024

Almost Linear Size Edit Distance Sketch.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Many Flavors of Edit Distance.

[BibT_eX]

[DOI]

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

Nearly Optimal List Labeling.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Automata and Formal Languages: Shall we let them go?

[BibT_eX]

[DOI]

Bull. EATCS, 2023

Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching.

[BibT_eX]

[DOI]

Sudatta Bhattacharya

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.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Streaming k-Edit Approximate Pattern Matching via String Decomposition.

[BibT_eX]

[DOI]

Sudatta Bhattacharya

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2021

Sorting Short Integers: The Exposition.

[BibT_eX]

[DOI]

Bull. EATCS, 2021

Barrington Plays Cards: The Complexity of Card-Based Protocols.

[BibT_eX]

[DOI]

Pavel Dvorák

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Sorting Short Integers.

[BibT_eX]

[DOI]

Karel Král

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Data Structures Lower Bounds and Popular Conjectures.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Computing Edit Distance (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual Symposium on Combinatorial Pattern Matching, 2021

Circuit complexity of regular languages.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Automata Theory., 2021

2020

Constant factor approximations to edit distance on far input pairs in nearly linear time.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Improved Bounds on Fourier Entropy and Min-Entropy.

[BibT_eX]

[DOI]

Srinivasan Arunachalam

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

2019

On Online Labeling with Large Label Set.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2019

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm.

[BibT_eX]

[DOI]

Vojtech Rödl

Navid Talebanfard

Electron. Colloquium Comput. Complex., 2019

Simulation Theorems via Pseudo-random Properties.

[BibT_eX]

[DOI]

Comput. Complex., 2019

Stronger Lower Bounds for Online ORAM.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 17th International Conference, 2019

Approximate Online Pattern Matching in Sublinear Time.

[BibT_eX]

[DOI]

Debarati Das

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.

[BibT_eX]

[DOI]

Chen Avin

Zvi Lotker

Random Struct. Algorithms, 2018

Approximate Online Pattern Matching in Sub-linear Time.

[BibT_eX]

[DOI]

Debarati Das

CoRR, 2018

Simulation beats richness: new data-structure lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication.

[BibT_eX]

[DOI]

Debarati Das

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

A Communication Game Related to the Sensitivity Conjecture.

[BibT_eX]

[DOI]

Justin Gilmer

Theory Comput., 2017

Composition and Simulation Theorems via Pseudo-random Properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2017

Optimal Quasi-Gray Codes: Does the Alphabet Matter?

[BibT_eX]

[DOI]

CoRR, 2017

Simulation Theorems via Pseudorandom Properties.

[BibT_eX]

[DOI]

CoRR, 2017

Lower Bounds for Elimination via Weak Regularity.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Expander Construction in VNC1.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Expander Construction in VNC1.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Catalytic computation.

[BibT_eX]

[DOI]

Bull. EATCS, 2016

The Big Match in Small Space.

[BibT_eX]

[DOI]

Rasmus Ibsen-Jensen

CoRR, 2016

Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees.

[BibT_eX]

[DOI]

CoRR, 2016

Streaming algorithms for embedding and computing edit distance in the low distance regime.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Catalytic Space: Non-determinism and Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

The Big Match in Small Space - (Extended Abstract).

[BibT_eX]

[DOI]

Rasmus Ibsen-Jensen

Proceedings of the Algorithmic Game Theory - 9th International Symposium, 2016

2015

Nonuniform catalytic space and the direct sum for space.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Low Distortion Embedding from Edit to Hamming Distance using Coupling.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

A New Approach to the Sensitivity Conjecture.

[BibT_eX]

[DOI]

Justin Gilmer

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

Information Complexity for Multiparty Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

Computing with a full memory: catalytic space.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

2013

On Randomized Online Labeling with Polynomially Many Labels.

[BibT_eX]

[DOI]

Jan Bulánek

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

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

[BibT_eX]

[DOI]

Nikolay K. Vereshchagin

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Exact Algorithms for Solving Stochastic Games

[BibT_eX]

[DOI]

CoRR, 2012

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.

[BibT_eX]

[DOI]

Anna Gál

Emanuele Viola

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Tight lower bounds for the online labeling problem.

[BibT_eX]

[DOI]

Jan Bulánek

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

On Online Labeling with Polynomially Many Labels.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

The Hardness of Being Private.

[BibT_eX]

[DOI]

Anil Ada

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2011

Pseudorandom generators for group products: extended abstract.

[BibT_eX]

[DOI]

Prajakta Nimbhorkar

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Exact algorithms for solving stochastic games: extended abstract.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Pseudorandom Generators for Group Products.

[BibT_eX]

[DOI]

Prajakta Nimbhorkar

Electron. Colloquium Comput. Complex., 2010

Book review.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2010

Derandomizing from Random Strings.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Winning Concurrent Reachability Games Requires Doubly-Exponential Patience.

[BibT_eX]

[DOI]

Peter Bro Miltersen

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

A New Characterization of ACC0 and Probabilistic CC0.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Many random walks are faster than one.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs).

[BibT_eX]

[DOI]

Chen Avin

Zvi Lotker

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Randomised Individual Communication Complexity.

[BibT_eX]

[DOI]

Harry Buhrman

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Amplifying Lower Bounds by Means of Self-Reducibility.

[BibT_eX]

[DOI]

Eric Allender

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Languages with Bounded Multiparty Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the STACS 2007, 2007

High Entropy Random Selection Protocols.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

Inverting Onto Functions and Polynomial Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2007

Circuit Complexity of Regular Languages.

[BibT_eX]

[DOI]

Proceedings of the Computation and Logic in the Real World, 2007

2006

Inverting onto functions might not be hard.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Incremental Branching Programs.

[BibT_eX]

[DOI]

Anna Gál

Pierre McKenzie

Proceedings of the Computer Science, 2006

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Bounded-depth circuits: separating wires from gates.

[BibT_eX]

[DOI]

Denis Thérien

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

[BibT_eX]

[DOI]

Eric Allender

Harry Buhrman

Electron. Colloquium Comput. Complex., 2004

What Can be Efficiently Reduced to the K-Random Strings?

[BibT_eX]

[DOI]

Eric Allender

Harry Buhrman

Proceedings of the STACS 2004, 2004

2003

Derandomization and Distinguishing Complexity.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Power from Random Strings.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n4.03).

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

Universal Traversal Sequences with Backtracking.

[BibT_eX]

[DOI]