ECCC-Report TR15-028https://eccc.weizmann.ac.il/report/2015/028Comments and Revisions published for TR15-028en-usFri, 27 Feb 2015 14:59:22 +0200
Paper TR15-028
| Relative Discrepancy does not separate Information and Communication Complexity |
Sophie Laplante,
Lila Fontes,
Iordanis Kerenidis,
Rahul Jain,
Mathieu Laurière,
Jérémie Roland
https://eccc.weizmann.ac.il/report/2015/028Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that in the non- distributional setting, the relative discrepancy bound they defined 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, resolving also an open question regarding the relation of the partition bound and information complexity. Last, we prove the equivalence between the adaptive relative discrepancy and the public-coin partition bound, which implies that the logarithm of the adaptive relative discrepancy bound is quadratically tight with respect to communication.Fri, 27 Feb 2015 14:59:22 +0200https://eccc.weizmann.ac.il/report/2015/028