萩原学（産業技術総合研究所）「線形計画法、グラフ、置換群、および長さ関数と関連する誤り訂正符号」
本講演では、符号理論のテーマの一つ「置換符号」の復号と構成に関する講演者の最近の成果を紹介する。置換符号は、変調の手段として、Slepianにより1960年代に考案された理論である。近年、Jiangらによりフラッシュメモリ符号化への応用が示唆され、その実装報告がPapandreauらによってなされるなど、世界的に注目されている。本講演では、置換符号のアルゴリズムに線形計画法を、符号の構成法にコンパクトグラフを応用する方法を述べる。前者は、名工大の和田山氏との共同研究でIEEE Trans. on ITに掲載予定(今年中)の成果、後者は一部をAMS at Univ. of Hawaii (Mar. 2012)で、一部をISIT2012(July 2012)で講演予定の成果に基づいたものである。上の復号はユークリッド距離上の最尤復号を多項式時間で達成するものである。さらにその応用として、endall-t au距離と呼ばれる対称群の転倒数から定義される距離上でも、同様の特性を与える符号の条件を述べる。とくに、それがParabolic subgroupで満たされることを述べる。この議論は、J. Kong氏との共同研究で、氏の修士論文の一部である。