Semidefinite code bounds based on quadruple distances

Dion C. Gijswijt, Hans D. Mittelmann, Alexander Schrijver
http://arxiv.org/abs/1005.4959

A(n,d)で長さnの01列の集合で，どの2つの間のハミング距離もd以上であるものの最大サイズを表すとする．この論文では半正定値計画法を使って，様々なnとdの値に対するA(n,d)の上界を更新している．出てくる半正定値計画問題は巨大なので，対称性を考慮することにより計算効率を上げている．また，倍精度の計算では数値精度が足りないらしく，4倍精度の計算ができるSDPAを使っている．符号理論，代数的組合せ論，群の表現論，最適化理論，数値計算といったいろいろな分野の知見を集めて得られた結晶に思える．