Abstract
Improving a result of K. Mehlhorn and E. M. Schmidt, a function f with deterministic communication complexity n**2 is shown to have Las Vegas communication complexity O(n). This is the best possible, because the deterministic complexity cannot be more than the square of the Las Vegas communication complexity for any function.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 178-181 |
| Number of pages | 4 |
| Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
| State | Published - 1987 |
All Science Journal Classification (ASJC) codes
- Software