All reports by Author Andrey Utis:

__
TR04-120
| 22nd November 2004
__

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis#### Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis

Alice and Bob want to know if two strings of length $n$ are

almost equal. That is, do they differ on at most $a$ bits?

Let $0\le a\le n-1$.

We show that any deterministic protocol, as well as any

error-free quantum protocol ($C^*$ version), for this problem

requires at ...
more >>>