Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOG RANK LOWER BOUND:
Reports tagged with Log Rank Lower Bound:
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

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 >>>




ISSN 1433-8092 | Imprint