Information Complexity Density and Simulation of Protocols
Information Complexity Density and Simulation of Protocols
复制标题
信息复杂度密度与协议模拟
DOI：
10.1109/tit.2017.2746859
复制
发表时间：
2017
影响因子：
2.5
通讯作者：
and Shun Watanabe
中科院分区：
文献类型：
--
作者：
Himanshu Tyagi; Shaileshh Bojja Venkatakrishnan;Pramod Viswanath;and Shun Watanabe
交互式协议的模拟需要使用交互式通信来产生协议的输出，以在固定的统计距离ε内。最近的工作提出，该协议的信息复杂性起着核心作用，在表征的最小数量的比特，各方必须交换一个成功的模拟，即分布式通信的复杂性模拟的协议。已经提出了几种仿真协议，其通信复杂度取决于仿真协议的信息复杂度。然而，在没有任何一般的分布式通信复杂性的下限，信息复杂性的核心作用是远远没有解决。我们填补了这一空白，并证明了ε-模拟协议的分布式通信复杂度是有界的信息复杂度密度的ε-尾λε，一个随机变量的信息复杂度作为其期望值。对于有界轮数的协议，我们给出了一个模拟协议，产生一个匹配的上界。因此，决定分布式通信复杂度的不是信息复杂度，而是λε.作为我们的界的应用，在产品协议的摊销机制中，我们确定了精确的二阶项，以及对ε的精确依赖性.对于一般的协议，如两个产品协议的混合物或摊销的情况下，当重复不独立，我们推导出一个一般公式的领先渐近项。这些结果锐化和显着扩展已知的结果在摊销制度。在单次发射机制中，我们的下限揭示了通信复杂度对ε的依赖性。我们用一个例子来说明这一点，这个例子表现出分布式通信复杂性和信息复杂性之间的任意分离，对于所有足够小的$\ep$。
A simulation of an interactive protocol entails the use of interactive communication to produce the output of the protocol to within a fixed statistical distance ε. Recent works have proposed that theinformation complexityof the protocol plays a central role in characterizing the minimum number of bits that the parties must exchange for a successful simulation, namely thedistributional communication complexityof simulating the protocol. Several simulation protocols have been proposed with communication complexity depending on the information complexity of the simulated protocol. However, in the absence of any general lower bounds for distributional communication complexity, the conjectured central role of information complexity is far from settled. We fill this gap and show that the distributional communication complexity of ε-simulating a protocol is bounded below by the ε-tail λεof theinformation complexity density, a random variable with information complexity as its expected value. For protocols with bounded number of rounds, we give a simulation protocol that yields a matching upper bound. Thus, it is not information complexity but λεthat governs the distributional communication complexity.As applications of our bounds, in the amortized regime for product protocols, we identify the exact second order term, together with the precise dependence on ε. For general protocols such as a mixture of two product protocols or for the amortized case when the repetitions are not independent, we derive a general formula for the leading asymptotic term. These results sharpen and significantly extend known results in the amortized regime. In the single-shot regime, our lower bound sheds light on the dependence of communication complexity on ε. We illustrate this with an example that exhibits an arbitrary separation between distributional communication complexity and information complexity for all sufficiently small $\ep$.