通信複雑性理論入門

• 泉 泰介

  名古屋工業大学工学部情報工学科

書誌事項

タイトル別名

• A Concise Tour of Communication Complexity Theory
• 基礎と情報理論からのアプローチ
• Fundamentals and Approaches from Information Theory

抄録

通信複雑性理論とは，複数のプレイヤ間に分散して保持されているデータに対して，何らかの大域的な関数計算を行いたいとき，プレイヤ間で交換しなければならないビット数の上下界を明らかにする理論である．本解説では，同理論の基礎について概説するとともに，強力かつ新たなアプローチとして近年注目を集める，情報理論的手法を用いた通信複雑性の限界解明手法について，その基本的なアイデアを紹介する．

収録刊行物

• ＩＥＩＣＥ　ＦＵＮＤＡＭＥＮＴＡＬＳ　ＲＥＶＩＥＷ

  ＩＥＩＣＥ　ＦＵＮＤＡＭＥＮＴＡＬＳ　ＲＥＶＩＥＷ 10 (1), 46-56, 2016

  一般社団法人 電子情報通信学会

キーワード

• 通信複雑性
• 計算量理論
• 情報理論

詳細情報

• CRID: 1390001205343649664
• NII論文ID: 130005161802
• DOI: 10.1587/essfr.10.1_46
• ISSN: 18820875
• Web Site: https://www.jstage.jst.go.jp/article/essfr/10/1/10_46/_pdf
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可