2026-07-23T14:35:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10298 2024-03-06T10:45:45Z ddc:004 open_access

A ZPP^NP[1] Lifting Theorem Watson, Thomas Query complexity communication complexity lifting 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Watson 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.59 urn:nbn:de:0030-drops-102989 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.59 eng https://creativecommons.org/licenses/by/3.0/legalcode