Summary: 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 [the first author et al., SIAM J. Comput. 47, No. 6, 2435–2450 (2018; Zbl 1409.68115)]. 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.
For the entire collection see [Zbl 1373.68018].