Query-to-communication lifting for BPP using inner product
Query-to-communication lifting for BPP using inner product
复制标题
使用内积将 BPP 的查询提升为通信
DOI：
10.4230/lipics.icalp.2019.35
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
T. Pitassi
中科院分区：
文献类型：
--
作者：
A. Chattopadhyay;Yuval Filmus;Sajin Koroth;Or Meir;T. Pitassi
我们证明了一种新的基于内积的随机化协议的查询到通信提升方法。这使得我们可以使用一个更小的装置，从而更有效地提升。在这项工作之前，由于Chattopadhyay等人和Wu等人的研究，人们只知道这种定理适用于确定性协议。由于G\“o\”os、Pitassi和Watson，随机协议中唯一的查询到通信提升结果使用了更大的索引工具。
We prove a new query-to-communication lifting for randomized protocols, with inner product as gadget. This allows us to use a much smaller gadget, leading to a more efficient lifting. Prior to this work, such a theorem was known only for deterministic protocols, due to Chattopadhyay et al. and Wu et al. The only query-to-communication lifting result for randomized protocols, due to G\"o\"os, Pitassi and Watson, used the much larger indexing gadget.
Our proof also provides a unified treatment of randomized and deterministic lifting. Most existing proofs of deterministic lifting theorems use a measure of information known as thickness. In contrast, G\"o\"os, Pitassi and Watson used blockwise min-entropy as a measure of information. Our proof uses the blockwise min-entropy framework to prove lifting theorems in both settings in a unified way.
影响因子：
1.4
作者：
Mika Göös;Pritish Kamath;T. Pitassi;Thomas Watson
通讯作者：
Mika Göös;Pritish Kamath;T. Pitassi;Thomas Watson
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas
BPP 的查询到通信提升
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas