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

整理番号	2023a017
種別	若手・学生研究-短期共同研究
研究計画題目	エクスパンダーグラフの新しい構成手法の確立とその応用2
研究代表者	佐竹 翔平（熊本大学 総合情報統括センター ・准教授）
研究分野のキーワード	エクスパンダーグラフ, 組合せ論・組合せ最適化, 群論, 整数論, 情報科学 (含 暗号理論, 符号理論, 理論計算機科学, 学習理論)
目的と期待される成果	エクスパンダーは、辺が少ないながらも、局所的な連結性が高いという、一見相反する2つの特徴をもつ興味深いグラフであり、効率的な情報伝達が可能なネットワークであることから、暗号理論、学習理論などの情報科学の幅広い分野への応用が知られている。しかしその明示的な構成には様々な課題があり、連結性の尺度である拡大定数も一般に評価が困難である。例えば代数的なアプローチとして、有限群からグラフを構成し、その代数構造に着目して拡大定数を評価する研究があるが、構成の明示性が強い一方、拡大定数の評価が群論、整数論などの未解決問題に帰着されることが多く、数学的に難しい。また、組合せ論・アルゴリズム的なアプローチによる構成も研究されるが、代数的な問題へのタックルは回避できるものの、代数的構造の情報がない分、構成の明示性や拡大定数の評価の良さが往々に落ちてしまう。 　本研究の目的は以下の2点である。 (i) 上述の代数的な構成と組合せ論・アルゴリズム的な構成をハイブリットさせ、両者の利点を抽出した新しい構成手法を編み出す。 (ii) エクスパンダーの暗号理論や機械学習などの情報科学への応用にも目を向け、構成したエクスパンダーの応用を検討する。 昨年度は, 群論・整数論などの代数的構成に関する分野と、グラフ理論・組合せ最適化などの組合せ論・アルゴリズム的構成に関する分野の研究交流を行うことができ、参加者間によるいくつかの共同研究も進行している。本年度は、下記の「関連する研究の経過」で述べる研究経過に基づき、進行中の共同研究に関する現状報告と議論のみならず、深層学習におけるニューラルネットワークの構成・実装等の新たなテーマに関しても議論する。
組織委員(研究集会) 参加者(短期共同利用)	相川 勇輔（三菱電機株式会社 情報技術総合研究所・研究員） 池松 泰彦（九州大学IMI・助教） 金井 佑真（株式会社 メルカリ・プロダクトマネージャー） Cid REYES BUSTOS （NTT基礎数学研究センタ・リサーチアソシエート） Hyungrok JO（横浜国立大学 先端科学高等研究院・特任助教） 見村 万佐人（東北大学 理学研究科・准教授） 矢澤 明喜子（九州大学IMI・助教） 佐竹 翔平（熊本大学 総合情報統括センター・准教授）

WEB