The corruption bound, log-rank, and communication complexity

摘要

We prove upper bounds on deterministic communication complexity in terms of log of the rank and simple versions of the corruption bound. Our bounds are a simplified version of the results of Gavinsky and Lovett [8], using the same set of tools. We also give an elementary proof for the upper bound on communication complexity in terms of rank proved by Lovett [18]. (C) 2018 Elsevier B.V. All rights reserved.