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.STACS.2019.59
URN: urn:nbn:de:0030-drops-102989
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10298/
Go to the corresponding LIPIcs Volume Portal

Watson, Thomas

A ZPP^NP[1] Lifting Theorem

pdf-format:
LIPIcs-STACS-2019-59.pdf (0.6 MB)

Abstract

The complexity class ZPP^{NP[1]} (corresponding to zero-error randomized algorithms with access to one NP oracle query) is known to have a number of curious properties. We further explore this class in the settings of time complexity, query complexity, and communication complexity.
- For starters, we provide a new characterization: ZPP^{NP[1]} equals the restriction of BPP^{NP[1]} where the algorithm is only allowed to err when it forgoes the opportunity to make an NP oracle query.
- Using the above characterization, we prove a query-to-communication lifting theorem, which translates any ZPP^{NP[1]} decision tree lower bound for a function f into a ZPP^{NP[1]} communication lower bound for a two-party version of f.
- As an application, we use the above lifting theorem to prove that the ZPP^{NP[1]} communication lower bound technique introduced by Göös, Pitassi, and Watson (ICALP 2016) is not tight. We also provide a "primal" characterization of this lower bound technique as a complexity class.

BibTeX - Entry

@InProceedings{watson:LIPIcs:2019:10298,
  author =	{Thomas Watson},
  title =	{{A ZPP^NP[1] Lifting Theorem}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{59:1--59:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10298},
  doi =		{10.4230/LIPIcs.STACS.2019.59},
  annote =	{Keywords: Query complexity, communication complexity, lifting}
}

Keywords: Query complexity, communication complexity, lifting
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

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