双方向通信を伴う分散計算における情報理論的解析手法の構築

点击翻译按钮获取中文摘要

通信複雑量の問題は計算機科学の基礎的な問題のひとつと考えられており，様々な関数に対する分散計算プロトコルの提案や，その最適性の検討が行われていた．特に最近になって，通信複雑量を解析するためのツールとして，情報複雑量が導入された．また，格パーティのデータが定常無記憶分布に従って発生するシンボル列で，計算したい関数がシンボルごとの関数のコピーである場合，通信複雑量は情報複雑量によって漸近的に特徴付けられることが明らかにされた．このような経緯から，通信複雑量の問題において，情報複雑量はデータ圧縮におけるエントロピーに匹敵する量だと考えられ重要視されていた．一方，情報理論ではデータの定常無記憶性等を仮定せずに性能解析を行う手法として，HanとVerduによって提案された情報スペクトル的方法が知られている．この方法では，例えばデータ圧縮の性能評価を行う際，エントロピーではなく，対数尤度として定義されるエントロピー密度とその裾確率が重要な役割を果たすことが知られている．このような事実を踏まえ，本年度の研究では、通信複雑量の新しい解析ツールとして情報複雑量密度を導入し、情報スペクトル的な方法により通信複雑量の問題に取り組んだ．特に、関数計算と密接に関連するプロトコルシミュレーションの問題において、プロトコルをシミュレーションするための通信複雑量が情報複雑量密度の裾確率によって特徴付けできることを明らかにした．