Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with communication models:
TR07-058 | 9th June 2007
Dmitry Gavinsky

Classical Interaction Cannot Replace a Quantum Message

Revisions: 1

We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (two-way) model.

more >>>

TR18-089 | 27th April 2018
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

Half-duplex communication complexity

Revisions: 2

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other ... more >>>

ISSN 1433-8092 | Imprint