第19回高木レクチャー招待講演
平成29年7月8日(土)15:40--16:40
平成29年7月9日(日)09:30--10:30
京都大学数理解析研究所大講義室420号室


情報の複雑性の理論とその応用
Mark Braverman
(Princeton University)


Abstract

この論文は、京都大学において2017年7月に行われる高木レクチャーに関する講義録である。

情報の複雑性および、その理論が通信複雑性にどのように関連しているか、についての高いレベルでの概要を与える。さらに、情報の複雑性に関するいくつかの基本的性質、および、それを用いた直和定理への応用や通信の限界の精密な評価への応用について議論する。最後に、いくつかの未解決問題と今後の方向を述べる。