| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428870 | Information Processing Letters | 2007 | 5 Pages |
Abstract
It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
