組合せ数学セミナー
発表内容の概要
電子透かしとは、動画や音楽等の電子コンテンツを配布する際に
予め各ユーザに対応した識別情報（「電子透かし符号」）を埋め込んで
おくことで、コンテンツを不正に複製・流布された際にその流出元を
特定する技術です。この電子透かしに対する攻撃法のうち、複数の
悪意あるユーザが協力して電子透かし符号を改竄または削除する
「結託攻撃」への耐性を持つ電子透かし符号として、「結託耐性符号」という
符号が提案され、現在盛んに研究されています。
今回の発表では、この電子透かしと結託耐性符号に関して、その背景や
問題意識、符号の構成法のうち特に組合せ論的な具体例の紹介と、
話者による最近の研究内容の紹介を行います。
LDPC符号という古典誤り訂正符号は、誤り訂正の理論限界に接近する高い能力と
復号計算コストの低さから、実用化の動きが盛んに広がっている。
その１つのクラス「擬似巡回LDPC符号」と呼ばれる対象は、短い符号長において
良い性能をもつ上、コンパクトに記述できるなどの長所を持ち、活発に研究され
ている。
本研究では、擬似巡回LDPC符号の理論を量子符号理論へ応用する手法を提案する。
本研究手法の持つ、代数的組合せ論テイストを楽しんでいただければ幸いで
ある。
ハブ空港配置問題は，ハブ空港の配置と，非ハブ空港のハブ空港への接続を
決定する問題であり，O'Kelly (1987)により2次整数計画問題として定式化
された．一方で，ハブ空港の配置は既知で，接続のみを決定する問題が
Sohn and Park (2000)において扱われている．彼らはハブ空港の数が3つ以上
であるとき，この問題がNP困難であることを示した．
本発表では，接続のみを決定する問題を扱う．まず，ハブ空港の数が一般の
場合に対して，簡潔な3-近似解法と，独立ラウンディングに基づく2-近似解
法を提案する．次に，ハブ空港が3つの場合に対して，従属ラウンディングに
基づく(4/3)-近似解法を提案する．最後に，2-近似解法と(4/3)-近似解法を
組み合わせることで，ハブ空港が3つの場合に対する(5/4)-近似解法が得ら
れることを示す．
本研究は，松井知己(中央大学)，齊藤廣大(JST, ERATO, 合原複雑数理モデル
プロジェクト)との共同研究です．
今回は，発表者が過去に作成したシェラビリティー判定プログラム
の実装上の工夫について解説する．基本的には逆探索を使って総調
べをするだけの単純な面白みの無い方法であるが，逆探索のための
各ステップを高速化するための工夫と，探索領域を狭めるための工
夫によってそれなりの速度で動くようになっており，これらについ
て紹介する．
(今回の話はあまり数学ではありません．)
以下では,単純かつ孤立点を持たないgraphだけを扱います. graph Gが与えら
れると, box complexと呼ばれるabstract simplicial complex B(G)を考える
ことができます. B(G)の定義から,多面体|B(G)|上に不動点を持たないZ_2-action
Z_2-indexを自然に定義することができ, それを用いてgraph Gの彩色数χ(G)
の下界が与えられることが知られています. 一方, いくつかのgraphの例を除
いて, box complexの幾何学的構造をその定義から直接捉えることは難しく,
box complexのZ_2-indexを計算する一般的な方法も知られていません.
graphの彩色数の下界を幾何学的な量で与える研究が進んだ背景の一つとし
て, 次の組合せ論の問題が位相幾何学を応用して解決されたことが挙げられます.
n,k∈Nで, k≦nとする. n個の元からなる集合Nのk個の元からなる部分集合
全体からなる集合族を次の規則でクラス分けをする, k個の元からなる2つの
部分集合K_1,K_2に対し, K_1∩ K_2=φならば, K_1とK_2は異なるクラスに
分ける.このとき,クラス分けに必要なクラスの数の最小値はいくつになるか？
上記の問題に対し, M. Kneserは(n-2k+2)個のクラスを用意して,具体的に上記
の規則に従ったクラス分けの方法を与え,これよりクラスの数を減らすことはで
きないと予想しました. 予想はL. Lov\'aszにより, Borsuk-Ulam の定理を用い
て解決されました.
本講演では,上述の研究の背景を紹介し, graph Gの組合せ論的構造とbox complex
B(G)の幾何学的構造の関わりについて得られた結果を述べようと思います.
(PDFファイル)
戻る