Collection Nexus Trimester - 2016 - Central Workshop
Organizer(s)
Date(s)
03/05/2024
How can we separate Information and Communication complexity?
How far can the information complexity of a function be from its communication complexity? We examine what currently known techniques might be used to show a separation between the two notions. First, we show that information complexity is larger than the relaxed partition bound and hence larger than most known communication lower bound techniques. Then, we look at relative discrepancy, which was recently used by Ganor et al. to provide a separation between information and communication for a specific input distribution, where on input of size n, the communication is logn, while the information is loglogn. We show that in the non-distributional setting, the relative discrepancy bound is, in fact, smaller than the information complexity, and hence it cannot be used to separate information and communication complexity. In addition, in the distributional case, we provide an equivalent linear program formulation for relative discrepancy and relate it to variants of the partition bound.
