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-024 | 3rd December 2018 02:09

Query-to-Communication Lifting for P^NP

RSS-Feed




Revision #1
Authors: Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Accepted on: 3rd December 2018 02:09
Downloads: 820
Keywords: 


Abstract:

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture $\text{P}^{\small\text{NP}}$ communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).


Paper:

TR17-024 | 16th February 2017 05:14

Query-to-Communication Lifting for P^NP





TR17-024
Authors: Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Publication: 16th February 2017 13:30
Downloads: 2002
Keywords: 


Abstract:

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture $\text{P}^{\small\text{NP}}$ communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).



ISSN 1433-8092 | Imprint