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

ACM Symposium on Principles of Distributed Computing (PODC)

On Information Complexity in the Broadcast Model

Mark Braverman, Rotem Oshman

Published Jul 17, 2015• 14 citations
Publisher

Abstract

Information complexity is the extension of classical information theory to the interactive setting, where instead of one-way transmission we are interested in back-and-forth communication. This approach has been very influential in communication complexity, where it enables us to prove powerful lower bounds by quantifying the amount of information the participants in the computation must reveal about their inputs. In this paper we study information complexity in the classical broadcast model: k parties with private inputs wish to compute some function of their inputs, and they communicate by sending messages (one at a time) over a broadcast channel. We measure how much information the players reveal about their inputs to an external observer. This is called external information cost.

DOI
10.1145/2767386.2767425

Related papers

Multi-Party Protocols, Information Complexity and Privacy

Iordanis Kerenidis, Adi Rosén, Florent Urrutia

We introduce a new information-theoretic measure, which we call Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: The Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; and an explicit calculation of the zero-error Public Information Complexity of the k -party, n -bit Parity function, where a player outputs the bitwise parity of the inputs. The latter result also establishes that the amount of randomness needed by a private protocol that computes this function is Ω ( n ).

arXiv:1606.06872•ACM Transactions on Computation Theory•Mar 17, 2019•2 citations

Information cost of quantum communication protocols

Iordanis Kerenidis, Mathieu Laurière, François Le Gall +1 more

In two-party quantum communication complexity, Alice and Bob receive some classical inputs and wish to compute some function that depends on both these inputs, while minimizing the communication. This model has found numerous applications in many areas of computer science. One notion that has received a lot of attention recently is the information cost of the protocol, namely how much information the players reveal about their inputs when they run the protocol. In the quantum world, it is not straightforward to define a notion of quantum information cost. We study two different notions and analyze their relation. We also provide new quantum protocols for the Inner Product function and for Private Information Retrieval, and show that protocols for Private Information Retrieval whose classical or quantum information cost for the user is zero can have exponentially different information cost for the server.

arXiv:1409.8488•Quantum Information and Computation•Mar 1, 2016•10 citations

Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity

Itay Hazan, Eyal Kushilevitz Z

Direct-sum questions in (two-party) communication complexity ask whether two parties, Alice and Bob, can compute the value of a function f on l inputs (x_1,y_1),...,(x_l,y_l) more efficiently than by applying the best protocol for f, independently on each input (x_i,y_i). In spite of significant efforts to understand these questions (under various communication-complexity measures), the general question is still far from being well understood. In this paper, we offer a multiparty view of these questions: The direct-sum setting is just a two-player system with Alice having inputs x_1,...,x_l, Bob having inputs y_1,...,y_l and the desired output is f(x_1,y_1),...,f(x_l,y_l). The naive solution of solving the l problems independently, is modeled by a network with l (disconnected) pairs of players Alice i and Bob i, with inputs x_i,y_i respectively, and communication only within each pair. Then, we consider an intermediate ("star") model, where there is one Alice having l inputs x_1,...,x_l and l players Bob_1,...,Bob_l holding y_1,...,y_l, respectively (in fact, we consider few variants of this intermediate model, depending on whether communication between each Bob i and Alice is point-to-point or whether we allow broadcast). Our goal is to get a better understanding of the relation between the two extreme models (i.e., of the two-party direct-sum question). If, for instance, Alice and Bob can do better (for some complexity measure) than solving the l problems independently, we wish to understand what intermediate model already allows to do so (hereby understanding the "source" of such savings). If, on the other hand, we wish to prove that there is no better solution than solving the l problems independently, then our approach gives a way of breaking the task of proving such a statement into few (hopefully, easier) steps. We present several results of both types. Namely, for certain complexity measures, communication problems f and certain pairs of models, we can show gaps between the complexity of solving f on l instances in the two models in question; while, for certain other complexity measures and pairs of models, we can show that such gaps do not exist (for any communication problem f). For example, we prove that if only point-to-point communication is allowed in the intermediate "star" model, then significant savings are impossible in the public-coin randomized setting. On the other hand, in the private-coin randomized setting, if Alice is allowed to broadcast messages to all Bobs in the "star" network, then some savings are possible. While this approach does not lead yet to new results on the original two-party direct-sum question, we believe that our work gives new insights on the already-known direct-sum results, and may potentially lead to more such results in the future.

Leibniz international proceedings in informatics•Jan 1, 2017•1 citation

Broadcast-Efficient Secure Multiparty Computation.

Juan A. Garay, Clint Givens, Rafail Ostrovsky

Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource

•Jan 1, 2012•3 citations

Privacy and Communication Complexity

Eyal Kushelvitz

Each of two parties $P_\mathcal{X} $ and $P_\matcal{Y} $ holds an n-bit input, x and y, respectively. They wish to privately compute the value of $f( x,y )$. That is, $P_\mathcal{X} $ should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value $f ( x,y )$, and similarly, $P_\mathcal{Y} $ should not learn any additional information about x. In this paper, the two following basic questions in the theory of private computations are considered: 1. Which functions can be privately computed? 2. What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every $1 \leq g ( n ) \leq 2\cdot ( 2^n - 1)$ there are functions that can be privately computed with $g( n )$-rounds of communication, but not with $( g ( n ) - 1 )$-rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the communication costs of nonprivate protocols. Interestingly, randomization helps neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.

SIAM Journal on Discrete Mathematics•May 1, 1992•118 citations

Interactive compression to external information

Mark Braverman, Gillat Kol

We describe a new way of compressing two-party communication protocols to get protocols with potentially smaller communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the participants’ private inputs to an observer that watches the communication, can be simulated by a new protocol that communicates at most poly(I) · loglog(C) bits. Our result is tight up to polynomial factors, as it matches the recent work separating communication complexity from external information cost.

ACM Symposium on Theory of Computing (STOC)•Jun 20, 2018•5 citations
Information complexity is the extension of classical information theory to the interactive setting, where instead of one-way transmission we are interested in back-and-forth communication. This approach has been very influential in communication complexity, where it enables us to prove powerful lower bounds by quantifying the amount of information the participants in the computation must reveal about their inputs. In this paper we study information complexity in the classical broadcast model: k parties with private inputs wish to compute some function of their inputs, and they communicate by sending messages (one at a time) over a broadcast channel. We measure how much information the players reveal about their inputs to an external observer. This is called external information cost.
We introduce a new information-theoretic measure, which we call Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: The Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; and an explicit calculation of the zero-error Public Information Complexity of the k -party, n -bit Parity function, where a player outputs the bitwise parity of the inputs. The latter result also establishes that the amount of randomness needed by a private protocol that computes this function is Ω ( n ).
In two-party quantum communication complexity, Alice and Bob receive some classical inputs and wish to compute some function that depends on both these inputs, while minimizing the communication. This model has found numerous applications in many areas of computer science. One notion that has received a lot of attention recently is the information cost of the protocol, namely how much information the players reveal about their inputs when they run the protocol. In the quantum world, it is not straightforward to define a notion of quantum information cost. We study two different notions and analyze their relation. We also provide new quantum protocols for the Inner Product function and for Private Information Retrieval, and show that protocols for Private Information Retrieval whose classical or quantum information cost for the user is zero can have exponentially different information cost for the server.
Direct-sum questions in (two-party) communication complexity ask whether two parties, Alice and Bob, can compute the value of a function f on l inputs (x_1,y_1),...,(x_l,y_l) more efficiently than by applying the best protocol for f, independently on each input (x_i,y_i). In spite of significant efforts to understand these questions (under various communication-complexity measures), the general question is still far from being well understood. In this paper, we offer a multiparty view of these questions: The direct-sum setting is just a two-player system with Alice having inputs x_1,...,x_l, Bob having inputs y_1,...,y_l and the desired output is f(x_1,y_1),...,f(x_l,y_l). The naive solution of solving the l problems independently, is modeled by a network with l (disconnected) pairs of players Alice i and Bob i, with inputs x_i,y_i respectively, and communication only within each pair. Then, we consider an intermediate ("star") model, where there is one Alice having l inputs x_1,...,x_l and l players Bob_1,...,Bob_l holding y_1,...,y_l, respectively (in fact, we consider few variants of this intermediate model, depending on whether communication between each Bob i and Alice is point-to-point or whether we allow broadcast). Our goal is to get a better understanding of the relation between the two extreme models (i.e., of the two-party direct-sum question). If, for instance, Alice and Bob can do better (for some complexity measure) than solving the l problems independently, we wish to understand what intermediate model already allows to do so (hereby understanding the "source" of such savings). If, on the other hand, we wish to prove that there is no better solution than solving the l problems independently, then our approach gives a way of breaking the task of proving such a statement into few (hopefully, easier) steps. We present several results of both types. Namely, for certain complexity measures, communication problems f and certain pairs of models, we can show gaps between the complexity of solving f on l instances in the two models in question; while, for certain other complexity measures and pairs of models, we can show that such gaps do not exist (for any communication problem f). For example, we prove that if only point-to-point communication is allowed in the intermediate "star" model, then significant savings are impossible in the public-coin randomized setting. On the other hand, in the private-coin randomized setting, if Alice is allowed to broadcast messages to all Bobs in the "star" network, then some savings are possible. While this approach does not lead yet to new results on the original two-party direct-sum question, we believe that our work gives new insights on the already-known direct-sum results, and may potentially lead to more such results in the future.
Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource
Each of two parties $P_\mathcal{X} $ and $P_\matcal{Y} $ holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x,y)f( x,y )f(x,y). That is, $P_\mathcal{X} $ should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value f(x,y)f ( x,y )f(x,y), and similarly, $P_\mathcal{Y} $ should not learn any additional information about x. In this paper, the two following basic questions in the theory of private computations are considered: 1. Which functions can be privately computed? 2. What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every 1≤g(n)≤2⋅(2n−1)1 \leq g ( n ) \leq 2\cdot ( 2^n - 1)1≤g(n)≤2⋅(2n−1) there are functions that can be privately computed with g(n)g( n )g(n)-rounds of communication, but not with (g(n)−1)( g ( n ) - 1 )(g(n)−1)-rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the communication costs of nonprivate protocols. Interestingly, randomization helps neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.
We describe a new way of compressing two-party communication protocols to get protocols with potentially smaller communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the participants’ private inputs to an observer that watches the communication, can be simulated by a new protocol that communicates at most poly(I) · loglog(C) bits. Our result is tight up to polynomial factors, as it matches the recent work separating communication complexity from external information cost.