Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems

Andris Ambainis; William Gasarch; Aravind Srinivasan; Andrey Utis

doi:10.1007/11940128_63

Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems

Andris Ambainis^*
, William Gasarch
, Aravind Srinivasan
, Andrey Utis

^*Corresponding author for this work

University of Waterloo
University of Maryland, College Park

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

Abstract

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≤ a≤n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C ^* version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q^* quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.

Original language	English
Title of host publication	Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings
Pages	628-637
Number of pages	10
DOIs	https://doi.org/10.1007/11940128_63
Publication status	Published - 2006
Externally published	Yes
Event	17th International Symposium on Algorithms and Computation, ISAAC 2006 - Kolkata, India Duration: 18 Dec 2006 → 20 Dec 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4288 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th International Symposium on Algorithms and Computation, ISAAC 2006
Country/Territory	India
City	Kolkata
Period	18/12/06 → 20/12/06

Access to Document

10.1007/11940128_63

Cite this

Ambainis, A., Gasarch, W., Srinivasan, A., & Utis, A. (2006). Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. In Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings (pp. 628-637). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4288 LNCS). https://doi.org/10.1007/11940128_63

Ambainis, Andris ; Gasarch, William ; Srinivasan, Aravind et al. / Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. pp. 628-637 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{31570366808d4ee494a7b30e3f615e89,

title = "Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems",

abstract = "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≤ a≤n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C * version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.",

author = "Andris Ambainis and William Gasarch and Aravind Srinivasan and Andrey Utis",

year = "2006",

doi = "10.1007/11940128\_63",

language = "English",

isbn = "3540496947",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "628--637",

booktitle = "Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings",

note = "17th International Symposium on Algorithms and Computation, ISAAC 2006 ; Conference date: 18-12-2006 Through 20-12-2006",

}

Ambainis, A, Gasarch, W, Srinivasan, A & Utis, A 2006, Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. in Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4288 LNCS, pp. 628-637, 17th International Symposium on Algorithms and Computation, ISAAC 2006, Kolkata, India, 18/12/06. https://doi.org/10.1007/11940128_63

Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. / Ambainis, Andris; Gasarch, William; Srinivasan, Aravind et al.
Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. p. 628-637 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4288 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems

AU - Ambainis, Andris

AU - Gasarch, William

AU - Srinivasan, Aravind

AU - Utis, Andrey

PY - 2006

Y1 - 2006

N2 - 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≤ a≤n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C * version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.

AB - 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≤ a≤n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C * version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.

UR - https://www.scopus.com/pages/publications/77249083717

U2 - 10.1007/11940128_63

DO - 10.1007/11940128_63

M3 - Conference paper

AN - SCOPUS:77249083717

SN - 3540496947

SN - 9783540496946

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 628

EP - 637

BT - Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings

T2 - 17th International Symposium on Algorithms and Computation, ISAAC 2006

Y2 - 18 December 2006 through 20 December 2006

ER -

Ambainis A, Gasarch W, Srinivasan A, Utis A. Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. In Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. p. 628-637. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11940128_63

Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this