Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-139 | 11th November 2020 03:08

A ZPP^NP[1] Lifting Theorem

RSS-Feed




Revision #1
Authors: Thomas Watson
Accepted on: 11th November 2020 03:08
Downloads: 319
Keywords: 


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 Goos, Pitassi, and Watson (ICALP 2016) is not tight. We also provide a "primal" characterization of this lower bound technique as a complexity class.


Paper:

TR17-139 | 18th September 2017 20:55

A ZPP^NP[1] Lifting Theorem





TR17-139
Authors: Thomas Watson
Publication: 18th September 2017 23:32
Downloads: 1264
Keywords: 


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 Goos, Pitassi, and Watson (ICALP 2016) is not tight. We also provide a "primal" characterization of this lower bound technique as a complexity class.



ISSN 1433-8092 | Imprint