文章基本信息

标题：Query-to-Communication Lifting for P^NP
本地全文：下载
作者：Mika G{\"o}{\"o}s ; Pritish Kamath ; Toniann Pitassi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：79
页码：12:1-12:16
DOI：10.4230/LIPIcs.CCC.2017.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：Communication Complexity; Query Complexity; Lifting Theorem; P^NP