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

整理番号	2024a028
種別	若手・学生研究-短期共同研究
研究計画題目	エクスパンダーグラフの新しい構成手法の確立とその応用3
研究代表者	佐竹 翔平（熊本大学 半導体・デジタル研究教育機構 総合情報学部門・准教授）
研究実施期間	2024年9月9日(月) ～ 2024年9月13日(金)
研究分野のキーワード	エクスパンダーグラフ, 組合せ論・組合せ最適化, 群論, 整数論, 耐量子計算機暗号, 符号理論, 理論計算機科学, 学習理論
目的と期待される成果	エクスパンダーは、辺が少ないながらも、局所的な連結性が高いという、一見相反する2つの特徴をもつ興味深いグラフであり、効率的な情報伝達が可能なネットワークであることや高速攪拌性から、(耐量子計算機)暗号、(量子)符号などの情報科学の幅広い分野への理論的応用が知られている。近年はグラフ構造をもつデータを扱う機械学習の分野などでもGoogleなどの企業がエクスパンダーの研究を進めており, 産業界での注目度も高まっている。しかしその明示的な構成は理論・応用の両面で不可欠でありながら様々な課題が残されており、連結性の尺度となるグラフの第2固有値も一般に評価が困難である。例えば代数的なアプローチとして、有限群からグラフを構成し、その代数構造に着目して第2固有値を評価する研究があるが、構成の明示性が強い一方、第2固有値の評価が群論、整数論などの未解決問題に帰着されることが多く、数学的に難しい。また、組合せ論・アルゴリズム的なアプローチによる構成も研究されるが、代数的な問題へのタックルは回避できるものの、代数的構造の情報がない分、構成の明示性や拡大定数の評価の良さが往々に落ちてしまう。 　本研究の目的は以下の2点である。 (i) 上述の代数的な構成と組合せ論・アルゴリズム的な構成をハイブリットさせ、両者の利点を抽出した新しい構成手法を編み出す。 (ii) エクスパンダーの暗号理論や機械学習などの情報科学への応用にも目を向け、構成したエクスパンダーの応用を検討する。 目的達成のため、まず群論・整数論・関数解析などの代数的構成に関する分野と、グラフ理論・組合せ最適化などの組合せ論・アルゴリズム的構成に関する分野の共同研究が必須である。昨年度までの共同研究は順調に進み、下記で述べるような研究成果も得られているが、目的達成のためにはさらなる共同研究が必要である。また、暗号理論、機械学習などの情報科学への応用研究は主に海外で活発に進展がみられる一方で、国内においてはまだまだ組織的な研究が少なく、また産業界へのプレゼンの余地も多くあることから、企業・大学の情報科学研究者を招いた共同研究の機会が依然として重要である。
組織委員(研究集会) 参加者(短期共同利用)	相川 勇輔（東京大学 情報理工学系研究科 ・助教） 池松 泰彦（九州大学IMI・助教） Cid Reyes Bustos（NTT基礎数学研究センタ・リサーチアソシエート） Hyungrok Jo（横浜国立大学 先端科学高等研究院・特任助教） 見村 万佐人（東北大学 理学研究科・准教授） 佐竹 翔平（熊本大学 半導体・デジタル研究教育機構・准教授）