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...
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 |
Similar Items
-
Communication complexity of permutation-invariant functions
by: Kamath, Pritish
Published: (2015) -
On the pseudo-deterministic query complexity of NP search problems
by: Goldwasser, S, et al.
Published: (2021) -
Role of Bis(triphenylphosphine)iminium Cation [PNP]+ on the Crystal Packing of [PNP]+[HSeO3]− Solvate Salt
by: Stefano Canossa, et al.
Published: (2018-03-01) -
An Empirical Study on the PNP Maritime Group Attrition System
by: Eugene V. Juaneza
Published: (2021-06-01) -
Sistem e-PnP Fakulti Teknologi Kejuruteraan
(FTK), UTHM
by: Sulaiman, Amelia, et al.
Published: (2021)