13 citations · 13 across the 1 of their papers we have counts for
4 papers
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…
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…
ARRIVAL: Next Stop in CLS
Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček +3
We study the computational complexity of ARRIVAL, a zero-player game on -vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the pr…
Ramsey numbers of ordered graphs
Martin Balko, Josef Cibulka, Karel Král +1
An ordered graph is a pair where is a graph and is a total ordering of its vertices. The ordered Ramsey number is th…