- 著者
-
泉 泰介
- 出版者
- 一般社団法人 電子情報通信学会
- 雑誌
- 電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review (ISSN:18820875)
- 巻号頁・発行日
- vol.10, no.1, pp.46-56, 2016-07-01 (Released:2016-07-02)
- 参考文献数
- 19
通信複雑性理論とは,複数のプレイヤ間に分散して保持されているデータに対して,何らかの大域的な関数計算を行いたいとき,プレイヤ間で交換しなければならないビット数の上下界を明らかにする理論である.本解説では,同理論の基礎について概説するとともに,強力かつ新たなアプローチとして近年注目を集める,情報理論的手法を用いた通信複雑性の限界解明手法について,その基本的なアイデアを紹介する.