3 papers
cs.CC2021
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…
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…
cs.CC2018
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…