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.ICALP.2017.52
URN: urn:nbn:de:0030-drops-74861
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7486/
Go to the corresponding LIPIcs Volume Portal

Göös, Mika ; Jayram, T. S. ; Pitassi, Toniann ; Watson, Thomas

Randomized Communication vs. Partition Number

pdf-format:
LIPIcs-ICALP-2017-52.pdf (0.6 MB)

Abstract

We show that randomized communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal randomized lower bounds for the Clique vs. Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (Goos, Pitassi, and Watson, FOCS 2015). One of our main technical contributions states that information complexity when the cost is measured with respect to only 1-inputs (or only 0-inputs) is essentially equivalent to information complexity with respect to all inputs.

BibTeX - Entry

@InProceedings{gs_et_al:LIPIcs:2017:7486,
  author =	{Mika G{\"o}{\"o}s and T. S. Jayram and Toniann Pitassi and Thomas Watson},
  title =	{{Randomized Communication vs. Partition Number}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7486},
  URN =		{urn:nbn:de:0030-drops-74861},
  doi =		{10.4230/LIPIcs.ICALP.2017.52},
  annote =	{Keywords: communication complexity, partition number, information complexity}
}

Keywords: communication complexity, partition number, information complexity
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

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