文章基本信息
- 标题：Query-to-Communication Lifting for P^NP
- 本地全文：下载
- 作者：Mika Göös ; Pritish Kamath ; Toniann Pitassi 等
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2017
- 卷号：2017
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
We prove that the P NP -type query complexity (alternatively, decision list width) of any boolean function f is quadratically related to the P 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 P NP communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).
