Interactive compression for product distributions
Interactive compression for product distributions
复制标题
产品分发的交互式压缩
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Gillat Kol
中科院分区：
文献类型：
--
作者：
Gillat Kol
我们研究交互式压缩问题：给定一个信息成本很小的两方通信协议，是否可以对其进行压缩，使得通信的总位数也很小？我们考虑各方具有彼此独立的输入的情况，并给出一个通信 I^2 * polylog(I) 位的模拟协议，其中 I 是原始协议的信息成本。我们的协议是第一个模拟协议，其通信复杂性受到原始协议信息成本多项式的限制。
We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol that communicates I^2 * polylog(I) bits, where I is the information cost of the original protocol. Our protocol is the first simulation protocol whose communication complexity is bounded by a polynomial in the information cost of the original protocol.