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.CCC.2018.9
URN: urn:nbn:de:0030-drops-88805
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8880/
Go to the corresponding LIPIcs Volume Portal

Watson, Thomas

Communication Complexity with Small Advantage

pdf-format:
LIPIcs-CCC-2018-9.pdf (0.6 MB)

Abstract

We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least epsilon greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed that the set-intersection function requires Theta(epsilon n) communication to achieve advantage epsilon. Building on this, we prove the same bound for several variants of set-intersection: (1) the classic "tribes" function obtained by composing with And (provided 1/epsilon is at most the width of the And), and (2) the variant where the sets are uniquely intersecting and the goal is to determine partial information about (say, certain bits of the index of) the intersecting coordinate.

BibTeX - Entry

@InProceedings{watson:LIPIcs:2018:8880,
  author =	{Thomas Watson},
  title =	{{Communication Complexity with Small Advantage}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8880},
  URN =		{urn:nbn:de:0030-drops-88805},
  doi =		{10.4230/LIPIcs.CCC.2018.9},
  annote =	{Keywords: Communication, complexity, small, advantage}
}

Keywords: Communication, complexity, small, advantage
Collection: 33rd Computational Complexity Conference (CCC 2018)
Issue Date: 2018
Date of publication: 04.06.2018

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