Query-to-Communication Lifting for PNP

Query-to-Communication Lifting for PNP

Abstract We prove that the PNP-type query complexity (alternatively, decision list width) of any Boolean function f is quadratically related to the PNP-type communication complexity of a lifted version of f. As an application, we show that a certain “product” lower bound method of Imp...

Full description

Bibliographic Details
Main Authors: Göös, Mika, Kamath, Pritish, Pitassi, Toniann, Watson, Thomas
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: Springer International Publishing 2021
Online Access:https://hdl.handle.net/1721.1/131537

Internet

https://hdl.handle.net/1721.1/131537

Similar Items