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}).
展开▼
机译：我们证明 emph {randomized}的通信复杂度在相关通信矩阵的分区号中可以是超对数的，并且得出了Clique vs. Independent Set问题的接近最佳 emph {randomized}的下界。这些结果加强了先前工作中获得的确定性下界（G “ o ” os，Pitassi和Watson，{ small FOCS〜2015}）。
展开▼
