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.2016.4
URN: urn:nbn:de:0030-drops-58471
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5847/
Go to the corresponding LIPIcs Volume Portal

Ambainis, Andris ; Kokainis, Martins ; Kothari, Robin

Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions

pdf-format:
26.pdf (0.5 MB)

Abstract

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity.

Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and Kothari. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from "lifting" the query separation to communication complexity.

BibTeX - Entry

@InProceedings{ambainis_et_al:LIPIcs:2016:5847,
  author =	{Andris Ambainis and Martins Kokainis and Robin Kothari},
  title =	{{Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Ran Raz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5847},
  URN =		{urn:nbn:de:0030-drops-58471},
  doi =		{10.4230/LIPIcs.CCC.2016.4},
  annote =	{Keywords: Query Complexity, Communication Complexity, Subcube Partition Complexity, Partition Bound}
}

Keywords: Query Complexity, Communication Complexity, Subcube Partition Complexity, Partition Bound
Collection: 31st Conference on Computational Complexity (CCC 2016)
Issue Date: 2016
Date of publication: 19.05.2016

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