Title
Randomized Communication vs. Partition Number.
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 (Goos, 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.
Year
Venue
DocType
2017
TOCT
Conference
Volume
Issue
Citations 
10
1
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Mika Göös120319.55
T. S. Jayram2137375.87
Toniann Pitassi32282155.18
Thomas Watson 000147311.27