2 citations · 3 across the 5 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.CC2020
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…
cs.CC2020
Parameterized Inapproximability of Independent Set in -Free Graphs
Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai +1
We study the Independent Set (IS) problem in -free graphs, i.e., graphs excluding some fixed graph as an induced subgraph. We prove several inapproximability results both fo…
cs.CC2020
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…