ECCC-Report TR14-132https://eccc.weizmann.ac.il/report/2014/132Comments and Revisions published for TR14-132en-usThu, 20 Nov 2014 06:20:04 +0200
Revision 2
| Information Complexity for Multiparty Communication |
Diptarka Chakraborty
https://eccc.weizmann.ac.il/report/2014/132#revision2In 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.Thu, 20 Nov 2014 06:20:04 +0200https://eccc.weizmann.ac.il/report/2014/132#revision2
Revision 1
| Information Complexity for Multiparty Communication |
Diptarka Chakraborty
https://eccc.weizmann.ac.il/report/2014/132#revision1In 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.Thu, 23 Oct 2014 14:55:38 +0300https://eccc.weizmann.ac.il/report/2014/132#revision1
Paper TR14-132
| Information Complexity for Multiparty Communication |
Diptarka Chakraborty,
Elazar Goldenberg,
Michal Koucky
https://eccc.weizmann.ac.il/report/2014/132In 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.Thu, 23 Oct 2014 12:23:47 +0300https://eccc.weizmann.ac.il/report/2014/132