Conference on Innovations in Theoretical Computer Science
Information Complexity Density and Simulation of Protocols
Himanshu Tyagi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath, Shun Watanabe
Abstract
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 the information complexity of the protocol plays a central role in characterizing the minimum number of bits that the parties must exchange for a successful simulation, namely the distributional communication complexity of 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 the information 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.