22 citations · 35 across the 10 of their papers we have counts for
19 papers
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm
Michal Koucký, Vojtěch Rödl, Navid Talebanfard
We show that for every there exists such that any -uniform hypergraph with edges and maximum vertex degree contains a set of at most $(\fra…
Data Structures Lower Bounds and Popular Conjectures
Pavel Dvořák, Michal Koucký, Karel Král +1
In this paper, we investigate the relative power of several conjectures that attracted recently lot of interest. We establish a connection between the Network Coding Conjecture (NC…
Barrington Plays Cards: The Complexity of Card-based Protocols
Pavel Dvořák, Michal Koucký
In this paper we study the computational complexity of functions that have efficient card-based protocols. Card-based protocols were proposed by den Boer [EUROCRYPT '89] as a means…
Constant factor approximations to edit distance on far input pairs in nearly linear time
Michal Koucký, Michael E. Saks
For any , there are constants and and a randomized algorithm that takes as input an integer and two strings of length at most , an…
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…
Approximate Online Pattern Matching in Sub-linear Time
Diptarka Chakraborty, Debarati Das, Michal Koucky
We consider the approximate pattern matching problem under edit distance. In this problem we are given a pattern of length and a text of length over some alphabet $…