| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 11023966 | Information Processing Letters | 2019 | 11 Pages |
Abstract
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].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Adi Shraibman,