エクスパンダーグラフの新しい構成手法の確立とその応用

整理番号 2022a017
種別 若手・学生研究-短期共同研究
研究計画題目 エクスパンダーグラフの新しい構成手法の確立とその応用
研究代表者 佐竹 翔平(明治大学総合数理学部・助教)
研究実施期間 2022年8月22日(月)~ 2022年8月26日(金)
研究分野のキーワード エクスパンダーグラフ, 組合せ最適化, 組合せ論, 群論, 整数論, 情報科学 (含 暗号理論, 学習理論)
目的と期待される成果 エクスパンダーは、辺が少ないながらも、局所的な連結性が高いという、一見相反する2つの特徴をもつ興味深いグラフであり、効率的な情報伝達が可能なネットワークであることから、暗号理論、学習理論などの情報科学の幅広い分野への応用が知られている。しかしその明示的な構成には様々な課題があり、連結性の尺度である拡大定数も一般に評価が困難である。例えば代数的なアプローチとして、有限群からグラフを構成し、その代数構造に着目して拡大定数を評価する研究があるが、構成の明示性が強い一方、拡大定数の評価が群論、整数論などの未解決問題に帰着されることが多く、数学的に難しい。また、組合せ論・アルゴリズム的なアプローチによる構成も研究されるが、代数的な問題へのタックルは回避できるものの、代数的構造の情報がない分、構成の明示性や拡大定数の評価の良さが往々に落ちてしまう。
 本研究の目的は以下の2点である。

(i) 上述の代数的な構成と組合せ論・アルゴリズム的な構成をハイブリットさせ、両者の利点を抽出した新しい構成手法を編み出す。
(ii) エクスパンダーの暗号理論や機械学習などの情報科学への応用にも目を向け、構成したエクスパンダーの応用を検討する。

目的達成のため、まず群論・整数論などの代数的構成に関する分野と、グラフ理論・組合せ最適化などの組合せ論・アルゴリズム的構成に関する分野の研究交流を行い、共同研究の下地を作る。こうした研究交流は、国内において、十分になされていなかったように思われる。本研究を通して、群論、整数論、組合せ論などの数学分野間の新たな交流が期待される。さらに、エクスパンダーの構成の応用を検討することで、実際の応用に求められるエクスパンダーの性質の数学的な定式化などから、関連する数学への新たな問題提供なども期待できる。
組織委員(研究集会)
参加者(短期共同利用)
池松 泰彦(九州大学IMI・助教)
金井 佑真(株式会社メルカリ・プロダクトマネージャー)
Jo Hyungrok(横浜国立大学 先端科学高等研究院・特任助教)
矢澤 明喜子(信州大学大学院・博士課程3年)
佐竹 翔平(明治大学総合数理学部・助教)
アドバイザー 神山 直之(九州大学マス・フォア・インダストリ研究所・教授)
WEB