符号理論と理論計算機科学の接点: グラフのカット問題を中心として

摘要

This tutorial explains a fundamental relationship between coding theory and graph-cut problems.%本講演では，理論計算機科学分野と符号理論分野で，独立した形で研究が進められている研究課題について，その繋がりを強調した紹介を試みたい．具体的には，グラフのカット（切断）に関する諸問題を符号理論の立場から，チュートリアル的に紹介するのが本稿の大きな目的である．特に線形計画復号法と最大カット発見アルゴリズムの間の関係，そして符号の基本多面体とカット多面体の関係，カットセット重み分布のアンサンブル平均などの話題に重点を置く．