Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Information Complexity Density and Simulation of Protocols Extended Abstract

Himanshu Tyagi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath, Shun Watanabe

Published Jan 1, 2016• 0 citations
OpenAlex

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 epsilon. 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 epsilon-simulating a protocol is bounded below by the epsilon-tail lambda(epsilon) 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 lambda(epsilon), 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 epsilon. 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 epsilon. We illustrate this with an example that exhibits an arbitrary separation between distributional communication complexity and information complexity for all sufficiently small epsilon.

Related papers

Information Complexity Density and Simulation of Protocols

Himanshu Tyagi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath +1 more

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.

Conference on Innovations in Theoretical Computer Science•Jan 5, 2016•3 citations

Information Complexity Density and Simulation of Protocols

Himanshu Tyagi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath +1 more

Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.

arXiv:1504.05666•IEEE Transactions on Information Theory•Aug 30, 2017•4 citations

Round Complexity of Common Randomness Generation: The Amortized Setting

Noah Golowich, Madhu Sudan

In this work we study the effect of rounds of interaction on the common randomness generation (CRG) problem. In the CRG problem, two parties, Alice and Bob, receive samples Xi and Yi, respectively, where (Xi, Yi) are drawn jointly from a source distribution μ. The two parties wish to agree on a common random key consisting of many bits of randomness, by exchanging messages that depend on each party's respective input and the previous messages. In this work we study the amortized version of the problem, i.e., the number of bits of communication needed per random bit output by Alice and Bob, in the limit as the number of bits generated tends to infinity. The amortized version of the CRG problem has been extensively studied in the information theory literature, though very little was known about the effect of interaction on this problem. Recently Bafna et al. (SODA 2019) considered the non-amortized version of the problem (so here the goal of the interaction is to generate a fixed number of random bits): they gave a family of sources μr,n parameterized by r,n ϵ ℕ, such that with r + 2 rounds of communication one can generate n bits of common randomness with this source with O(r log n) communication, whereas with roughly r/2 rounds the communication complexity is Ω(n/ poly log n). Note in particular that their source is designed with the target number of bits in mind and hence the result does not apply to the amortized setting. In this work we strengthen the work of Bafna et al. in two ways: First we show that the results extend to the classical amortized setting. We also reduce the gap between the round complexity in the upper and lower bounds to an additive constant. Specifically we show that for every pair r, n ϵ ℕ the (amortized) communication complexity to generate Ω(n) bits of common randomness from the source μr,n using r + 2 rounds of communication is O(r log n) whereas the amortized communication required to generate the same amount of randomness from r rounds is . Our techniques exploit known connections between information complexity and CRG, and the main novelty is our ability to analyze the information complexity of protocols getting inputs from the source μr,n.

arXiv:1909.00323•Society for Industrial and Applied Mathematics eBooks•Dec 23, 2019•3 citations

Lower bounds for interactive function computation via Wyner common information

Shijin Rajakrishnan, Sundara Rajan S, Vinod M. Prabhakaran

The question of how much communication is required between collaborating parties to compute a function of their data is of fundamental importance in the fields of theoretical computer science and information theory. In this work, the focus is on coming up with lower bounds on this. The information cost of a protocol is the amount of information the protocol reveals to Alice and Bob about each others inputs, and the information complexity of a function is the infimum of information costs over all valid protocols. For the amortized case, it is known that the optimal rate for the computation is equal to the information complexity. Exactly computing this information complexity is not straight forward however. In this work we lower bound information complexity for independent inputs in terms of the Wyner common information of a certain pair of random variables. We show a structural property for the optimal auxiliary random variable of Wyner common information and exploit this to exactly compute the Wyner common information in certain cases. The lower bound obtained through this technique is shown to be tight for a non-trivial example - equality (EQ) for the ternary alphabet. We also give an example to show that the lower bound may, in general, not be tight.

arXiv:1602.02390•National Conference on Communications•Mar 1, 2016•0 citations

Quantum Information Complexity and Amortized Communication

Dave Touchette

We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Ω(n/M + M), for M-message protocols. This would match the best known upper bound.

arXiv:1404.3733•Apr 14, 2014•16 citations

Interactive Communication for Data Exchange

Himanshu Tyagi, Pramod Viswanath, Shun Watanabe

Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.

IEEE Transactions on Information Theory•Nov 2, 2017•6 citations
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 epsilon. 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 epsilon-simulating a protocol is bounded below by the epsilon-tail lambda(epsilon) 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 lambda(epsilon), 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 epsilon. 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 epsilon. We illustrate this with an example that exhibits an arbitrary separation between distributional communication complexity and information complexity for all sufficiently small epsilon.
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.
Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.
In this work we study the effect of rounds of interaction on the common randomness generation (CRG) problem. In the CRG problem, two parties, Alice and Bob, receive samples Xi and Yi, respectively, where (Xi, Yi) are drawn jointly from a source distribution μ. The two parties wish to agree on a common random key consisting of many bits of randomness, by exchanging messages that depend on each party's respective input and the previous messages. In this work we study the amortized version of the problem, i.e., the number of bits of communication needed per random bit output by Alice and Bob, in the limit as the number of bits generated tends to infinity. The amortized version of the CRG problem has been extensively studied in the information theory literature, though very little was known about the effect of interaction on this problem. Recently Bafna et al. (SODA 2019) considered the non-amortized version of the problem (so here the goal of the interaction is to generate a fixed number of random bits): they gave a family of sources μr,n parameterized by r,n ϵ ℕ, such that with r + 2 rounds of communication one can generate n bits of common randomness with this source with O(r log n) communication, whereas with roughly r/2 rounds the communication complexity is Ω(n/ poly log n). Note in particular that their source is designed with the target number of bits in mind and hence the result does not apply to the amortized setting. In this work we strengthen the work of Bafna et al. in two ways: First we show that the results extend to the classical amortized setting. We also reduce the gap between the round complexity in the upper and lower bounds to an additive constant. Specifically we show that for every pair r, n ϵ ℕ the (amortized) communication complexity to generate Ω(n) bits of common randomness from the source μr,n using r + 2 rounds of communication is O(r log n) whereas the amortized communication required to generate the same amount of randomness from r rounds is . Our techniques exploit known connections between information complexity and CRG, and the main novelty is our ability to analyze the information complexity of protocols getting inputs from the source μr,n.
The question of how much communication is required between collaborating parties to compute a function of their data is of fundamental importance in the fields of theoretical computer science and information theory. In this work, the focus is on coming up with lower bounds on this. The information cost of a protocol is the amount of information the protocol reveals to Alice and Bob about each others inputs, and the information complexity of a function is the infimum of information costs over all valid protocols. For the amortized case, it is known that the optimal rate for the computation is equal to the information complexity. Exactly computing this information complexity is not straight forward however. In this work we lower bound information complexity for independent inputs in terms of the Wyner common information of a certain pair of random variables. We show a structural property for the optimal auxiliary random variable of Wyner common information and exploit this to exactly compute the Wyner common information in certain cases. The lower bound obtained through this technique is shown to be tight for a non-trivial example - equality (EQ) for the ternary alphabet. We also give an example to show that the lower bound may, in general, not be tight.
We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Ω(n/M + M), for M-message protocols. This would match the best known upper bound.
Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.