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

High Entropy Random Selection Protocols.

[BibT_eX]

[DOI]

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

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time.

[BibT_eX]

[DOI]

J. ACM, 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

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

Catalytic Space: Non-determinism and Hierarchy.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

Improved bounds on Fourier entropy and Min-entropy.

[BibT_eX]

[DOI]

Srinivasan Arunachalam

Electron. Colloquium Comput. Complex., 2018

Approximate Online Pattern Matching in Sub-linear Time.

[BibT_eX]

[DOI]

Debarati Das

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

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

Simulation Beats Richness: New Data-Structure Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Expander Construction in VNC1.

[BibT_eX]

[DOI]

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

2016

Lower Bounds for Elimination via Weak Regularity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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

[BibT_eX]

[DOI]

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

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

Tight Lower Bounds for the Online Labeling Problem.

[BibT_eX]

[DOI]

Jan Bulánek

SIAM J. Comput., 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

The Hardness of Being Private.

[BibT_eX]

[DOI]

Anil Ada

ACM Trans. Comput. Theory, 2014

Information Complexity for Multiparty Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Computing with a full memory: Catalytic space.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 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

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

On Online Labeling with Polynomially Many Labels.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

2011

The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

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

[BibT_eX]

[DOI]

Anna Gál

Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2011

Many Random Walks Are Faster Than One.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 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

A New Characterization of ACC0 and Probabilistic CC0.

[BibT_eX]

[DOI]

Comput. Complex., 2010

Derandomizing from Random Strings.

[BibT_eX]

[DOI]

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

2009

Circuit Complexity of Regular Languages.

[BibT_eX]

[DOI]

Theory Comput. Syst., 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

2008

Amplifying Lower Bounds by Means of Self-Reducibility.

[BibT_eX]

[DOI]

Eric Allender

Electron. Colloquium Comput. Complex., 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

2007

Inverting Onto Functions and Polynomial Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2007

2006

Power from Random Strings.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Languages with Bounded Multiparty Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Inverting onto functions might not be hard.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Incremental branching programs

[BibT_eX]

[DOI]

Anna Gál

Pierre McKenzie

Electron. Colloquium Comput. Complex., 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

Log-space constructible universal traversal sequences for cycles of length O(n4.03).

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Derandomization and Distinguishing Complexity.

[BibT_eX]

[DOI]

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

2002

Universal traversal sequences with backtracking.

[BibT_eX]

[DOI]