Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CONSTANT ROUND COMMUNICATION COMPLEXITY:
Reports tagged with Constant Round Communication Complexity:
TR21-030 | 2nd March 2021
Shuichi Hirahara, Rahul Ilango, Bruno Loff

Hardness of Constant-round Communication Complexity

How difficult is it to compute the communication complexity of a two-argument total Boolean function $f:[N]\times[N]\to\{0,1\}$, when it is given as an $N\times N$ binary matrix? In 2009, Kushilevitz and Weinreb showed that this problem is cryptographically hard, but it is still open whether it is NP-hard.

In this ... more >>>




ISSN 1433-8092 | Imprint