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
Fingerprint
Dive into the research topics of 'POWER OF RANDOMNESS FOR COMMUNICATION COMPLEXITY.'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver