Скачать или смотреть Communication Complexity is NP-hard (Theory of Computing Seminar 001, July 20, 2023)

Abstract:
I will show that computing the communication complexity of a given Boolean matrix is NP-hard.

The proof consists of a small collection of somewhat delicate observations, on top of a previous reduction by Jiang and Ravikumar, who implicitly (using a different language) showed that the 1-partition number chi_1(f) is NP-hard to compute given f.

The result is somewhat brittle, as it only works for the problem of computing the communication complexity exactly, i.e., we get no hardness of approximation, not even ± 1. Nonetheless, this answers an open question asked by Andrew Yao in the very first paper where communication complexity was defined (STOC 1979, "Some Complexity Questions Related to Distributive Computing").

This is joint work with Rahul Ilango and Shuichi Hirahara.