ECCC-Report TR21-030https://eccc.weizmann.ac.il/report/2021/030Comments and Revisions published for TR21-030en-usTue, 02 Mar 2021 23:31:00 +0200
Paper TR21-030
| Hardness of Constant-round Communication Complexity |
Rahul Ilango,
Shuichi Hirahara,
Bruno Loff
https://eccc.weizmann.ac.il/report/2021/030How 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 work, we show that it is NP-hard to approximate the size (number of leaves) of the smallest constant-round protocol for a two-argument total Boolean function $f:[N]\times[N]\to\{0,1\}$, when it is given as an $N\times N$ binary matrix. Along the way to proving this, we show a new *deterministic* variant of the round elimination lemma, which may be of independent interest. Tue, 02 Mar 2021 23:31:00 +0200https://eccc.weizmann.ac.il/report/2021/030