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…
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…
Lower Bounds for Semi-adaptive Data Structures via Corruption
Pavel Dvořák, Bruno Loff
In a dynamic data structure problem we wish to maintain an encoding of some data in memory, in such a way that we may efficiently carry out a sequence of queries and updates to the…
On Induced Online Ramsey Number of Paths, Cycles, and Trees
Václav Blažej, Pavel Dvořák, Tomáš Valla
An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a graph and a graph of an infinite set of independent vertices. In each ro…