SCIENCE@home

A ZPPNP[1] Lifting Theorem

Thomas Watson

Published 2020 in Symposium on Theoretical Aspects of Computer Science

ABSTRACT

The complexity class ZPPNP[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: ZPPNP[1] equals the restriction of BPPNP[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 ZPPNP[1] decision tree lower bound for a function f into a ZPPNP[1] communication lower bound for a two-party version of f. • As an application, we use the above lifting theorem to prove that the ZPPNP[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.

PUBLICATION RECORD

  • Publication year

    2020

  • Venue

    Symposium on Theoretical Aspects of Computer Science

  • Publication date

    2020-11-08

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    DOI 10.1145/3428673
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-53 of 53 references · Page 1 of 1

CITED BY