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.
De Sidharth Jaggi
De Maxim Raginsky
De David Woodruff
De Ankit Garg
De Ran Gelles
De Iordanis Kerenidis
De Sidharth Jaggi
De Giacomo Como
De Gérard Ben Arous
De Giulio Biroli
De Giulio Biroli
De Gérard Ben Arous
