Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-169 | 23rd October 2015 01:27

Randomized Communication vs. Partition Number

RSS-Feed




TR15-169
Authors: Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson
Publication: 23rd October 2015 03:25
Downloads: 836
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