Michal Kouck'y

collaborators

3 papers

cs.DS2023

Streaming $k$ -edit approximate pattern matching via string decomposition

Sudatta Bhattacharya, Michal Koucký

In this paper we give an algorithm for streaming $k$ -edit approximate pattern matching which uses space $O (k^{2})$ and time $O (k^{2})$ per arriving symbol. This…

cs.DS2023

Locally consistent decomposition of strings with applications to edit distance sketching

Sudatta Bhattacharya, Michal Koucký

In this paper we provide a new locally consistent decomposition of strings. Each string $x$ is decomposed into blocks that can be described by grammars of size $O (k)$ (…

cs.CC2021

Sorting Short Integers

Michal Koucký, Karel Král

We build boolean circuits of size $O (n m^{2})$ and depth $O (lo g (n) + m lo g (m))$ for sorting $n$ integers each of $m$ -bits. We build also circuits that sort $n$ integers each of $m$ -…

Streaming k-edit approximate pattern matching via string decomposition

Locally consistent decomposition of strings with applications to edit distance sketching

Sorting Short Integers

Streaming $k$ -edit approximate pattern matching via string decomposition