License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.7
URN: urn:nbn:de:0030-drops-95893
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9589/
Go to the corresponding LIPIcs Volume Portal

Klenin, Egor ; Kozachinskiy, Alexander

One-Sided Error Communication Complexity of Gap Hamming Distance

pdf-format:
LIPIcs-MFCS-2018-7.pdf (0.4 MB)

Abstract

Assume that Alice has a binary string x and Bob a binary string y, both strings are of length n. Their goal is to output 0, if x and y are at least L-close in Hamming distance, and output 1, if x and y are at least U-far in Hamming distance, where L < U are some integer parameters known to both parties. If the Hamming distance between x and y lies in the interval (L, U), they are allowed to output anything. This problem is called the Gap Hamming Distance. In this paper we study public-coin one-sided error communication complexity of this problem. The error with probability at most 1/2 is allowed only for pairs at Hamming distance at least U. In this paper we determine this complexity up to factors logarithmic in L. The protocol we construct for the upper bound is simultaneous.

BibTeX - Entry

@InProceedings{klenin_et_al:LIPIcs:2018:9589,
  author =	{Egor Klenin and Alexander Kozachinskiy},
  title =	{{One-Sided Error Communication Complexity of Gap Hamming Distance}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9589},
  URN =		{urn:nbn:de:0030-drops-95893},
  doi =		{10.4230/LIPIcs.MFCS.2018.7},
  annote =	{Keywords: Communication Complexity, Gap Hamming Distance, one-sided error}
}

Keywords: Communication Complexity, Gap Hamming Distance, one-sided error
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI