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-050 | 15th May 2018 02:00

Deterministic Communication vs. Partition Number

RSS-Feed




Revision #1
Authors: Mika Göös, Toniann Pitassi, Thomas Watson
Accepted on: 15th May 2018 02:00
Downloads: 949
Keywords: 


Abstract:

We show that deterministic communication complexity can be superlogarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the Clique vs. Independent Set problem, which in particular yields new lower bounds for the log-rank conjecture. All these results follow from a simple adaptation of a communication-to-query simulation theorem of Raz and McKenzie (Combinatorica 1999) together with lower bounds for the analogous query complexity questions.


Paper:

TR15-050 | 4th April 2015 23:15

Deterministic Communication vs. Partition Number





TR15-050
Authors: Mika Göös, Toniann Pitassi, Thomas Watson
Publication: 4th April 2015 23:25
Downloads: 3167
Keywords: 


Abstract:

We show that deterministic communication complexity can be superlogarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the Clique vs. Independent Set problem, which in particular yields new lower bounds for the log-rank conjecture. All these results follow from a simple adaptation of a communication-to-query simulation theorem of Raz and McKenzie (Combinatorica 1999) together with lower bounds for the analogous query complexity questions.



ISSN 1433-8092 | Imprint