Revision #2 Authors: Diptarka Chakraborty

Accepted on: 20th November 2014 06:20

Downloads: 717

Keywords:

In this paper, we have studied the information complexity for the communication model involving more than two parties. A lot of work has already been done on the information complexity in two party communication model and the question of extending the definition of information complexity to the multiparty communication model was posed in \cite{Braverman12}. In this paper, we first give a definition of internal information cost for a protocol involving more than two parties and our definition matches the definition known for two party model. Our definition is valid for both in NIH model and NOF model. We also extend several results known for information complexity of two party model to multiparty communication setting. We show that our definition of information complexity is sub-additive in nature. We give a lower bound for the information complexity of a function involving more that two parties in terms of communication complexity and this lower bound matches with the bound known for the function evaluated by only two parties. We also show that the amortized communication complexity of a function computed by $k$ parties is upper bounded by $(k-1)$ times the information complexity and this relation is true for both distributional and non-distributional case.

Revision #1 Authors: Diptarka Chakraborty

Accepted on: 23rd October 2014 14:55

Downloads: 693

Keywords:

In this paper, we have studied the information complexity for the communication model involving more than two parties. A lot of work has already been done on the information complexity in two party communication model and the question of extending the definition of information complexity to the multiparty communication model was posed in \cite{Braverman12}. In this paper, we first give a definition of internal information cost for a protocol involving more than two parties and our definition matches the definition known for two party model. Our definition is valid for both in NIH model and NOF model. We also extend several results known for information complexity of two party model to multiparty communication setting. One of them is the additivity property, which eventually gives us the direct sum theorem for both information cost and distributional information cost. We give a lower bound for the information complexity of a function involving more that two parties in terms of communication complexity and this lower bound matches with the bound known for the function evaluated by only two parties. We also show that the amortized communication complexity of a function computed by $k$ parties is lower bounded by the information complexity and upper bounded by $(k-1)$ times the information complexity and this relation is true for both distributional and non-distributional case.

TR14-132 Authors: Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

Publication: 23rd October 2014 12:23

Downloads: 964

Keywords:

In this paper, we have studied the information complexity for the communication model involving more than two parties. A lot of work has already been done on the information complexity in two party communication model and the question of extending the definition of information complexity to the multiparty communication model was posed in \cite{Braverman12}. In this paper, we first give a definition of internal information cost for a protocol involving more than two parties and our definition matches the definition known for two party model. Our definition is valid for both in NIH model and NOF model. We also extend several results known for information complexity of two party model to multiparty communication setting. One of them is the additivity property, which eventually gives us the direct sum theorem for both information cost and distributional information cost. We give a lower bound for the information complexity of a function involving more that two parties in terms of communication complexity and this lower bound matches with the bound known for the function evaluated by only two parties. We also show that the amortized communication complexity of a function computed by $k$ parties is lower bounded by the information complexity and upper bounded by $(k-1)$ times the information complexity and this relation is true for both distributional and non-distributional case.