情報の複雑性の理論とその応用 高木レクチャー講演録 M. ブレーバーマン
情報の複雑性の理論とその応用 高木レクチャー講演録
M. ブレーバーマン
Abstract: この論文は,京都大学において2017年7月に行われる高木レクチャーに関する講義録である.
情報の複雑性および,その理論が通信複雑性にどのように関連しているか,についての高いレベルでの概要を与える.さらに,情報の複雑性に関するいくつかの基本的性質,および,それを用いた直和定理への応用や通信の限界の精密な評価への応用について議論する.最後に,いくつかの未解決問題と今後の方向を述べる.