9 citations · 9 across the 4 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
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.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.CC2018
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
Debarati Das, Michal Koucký, Michael Saks
In this paper we propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a r…