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.2020.92
URN: urn:nbn:de:0030-drops-124992
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12499/
Go to the corresponding LIPIcs Volume Portal

Pitassi, Toniann ; Shirley, Morgan ; Watson, Thomas

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

pdf-format:
LIPIcs-ICALP-2020-92.pdf (0.6 MB)

Abstract

We investigate the power of randomness in two-party communication complexity. In particular, we study the model where the parties can make a constant number of queries to a function with an efficient one-sided-error randomized protocol. The complexity classes defined by this model comprise the Randomized Boolean Hierarchy, which is analogous to the Boolean Hierarchy but defined with one-sided-error randomness instead of nondeterminism. Our techniques connect the Nondeterministic and Randomized Boolean Hierarchies, and we provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove that the Randomized Boolean Hierarchy does not collapse, and we prove a query-to-communication lifting theorem for all levels of the Nondeterministic Boolean Hierarchy and use it to resolve an open problem stated in the paper by Halstenberg and Reischuk (CCC 1988) which initiated the study of this hierarchy.

BibTeX - Entry

@InProceedings{pitassi_et_al:LIPIcs:2020:12499,
  author =	{Toniann Pitassi and Morgan Shirley and Thomas Watson},
  title =	{{Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{92:1--92:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12499},
  URN =		{urn:nbn:de:0030-drops-124992},
  doi =		{10.4230/LIPIcs.ICALP.2020.92},
  annote =	{Keywords: Boolean hierarchies, lifting theorems, query complexity}
}

Keywords: Boolean hierarchies, lifting theorems, query complexity
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

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