M. Koucký

activity

20072021

most citedApproximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

22 citations · 35 across the 10 of their papers we have counts for

collaborators

Showing 2019Show all

2 papers · 1 filter

cs.DS2019

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

Michal Koucký, Michael E. Saks

For any $T \geq 1$ , there are constants $R = R (T) \geq 1$ and $ζ = ζ (T) > 0$ and a randomized algorithm that takes as input an integer $n$ and two strings $x, y$ of length at most $n$ , an…

cs.CR2019

Stronger Lower Bounds for Online ORAM

Pavel Hubáček, Michal Koucký, Karel Král +1

Oblivious RAM (ORAM), introduced in the context of software protection by Goldreich and Ostrovsky [JACM'96], aims at obfuscating the memory access pattern induced by a RAM computat…