"Computing Constant-round Communication Complexity is Hard"
Rahul Ilango (MIT)
Monday, April 26th 2021, 2-3pm
Abstract:
How difficult is it to compute the communication complexity of a given two-player Boolean function (represented as an N x N matrix)? In 2009, Kushilevitz and Weinreb showed cryptographic hardness for this problem, but it is still open whether it is NP-hard. Moreover, proving optimal hardness of approximation for this problem has intriguing implications on the log rank conjecture of Lovász and Saks .
In this talk, I will briefly recap this motivation and then discuss recent joint work with Shuichi Hirahara and Bruno Loff that shows it is NP-hard to approximate the size (number of leaves) of the smallest *constant-round* protocol for a given Boolean function. I will also highlight one of the main techniques used in our proof: a new *deterministic* variant of the round elimination lemma.