Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-169 | 5th January 2018 07:44

Randomized Communication vs. Partition Number

RSS-Feed




Revision #1
Authors: Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson
Accepted on: 5th January 2018 07:44
Downloads: 933
Keywords: 


Abstract:

We show that randomized communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal randomized lower bounds for the Clique vs. Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, FOCS 2015). One of our main technical contributions states that information complexity when the cost is measured with respect to only 1-inputs (or only 0-inputs) is essentially equivalent to information complexity with respect to all inputs.


Paper:

TR15-169 | 23rd October 2015 01:27

Randomized Communication vs. Partition Number





TR15-169
Authors: Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson
Publication: 23rd October 2015 03:25
Downloads: 1916
Keywords: 


Abstract:

We show that \emph{randomized} communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal \emph{randomized} lower bounds for the Clique vs.\ Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, {\small FOCS~2015}).



ISSN 1433-8092 | Imprint