革新的アルゴリズム基盤の構築に向けて

【略歴】2000年東京大学大学院理学系研究科博士課程修了．2000年東北大学助手，2003年九州大学助教授，2009年国立情報学研究所准教授，教授を経て2014年より現職．
2020年度-2021年度 情報処理学会アルゴリズム研究会主査．2011年度 情報処理学会論文誌ジャーナル/JIP基盤グループ主査．
日本IBM科学賞，ドコモ・モバイル・サイエンス賞，日本学術振興会賞，文部科学大臣表彰 科学技術賞受賞．

【講演概要】現代の高度情報化社会を動かしているアルゴリズム技術の進展を，様々な分野の科学者・技術者が理解可能な形で広く自由に利用できる学術として体系化し，社会変革の源泉となる基盤研究領域として発展させることを目的として，2020 年11 月に科研費・学術変革領域研究（A）「社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化」が採択され，研究活動が開始された．本研究領域は，近年の圧倒的な計算性能の進歩や未来の革新的デバイス，及び新しい社会的概念や価値観に基づいて，理論と応用を分かりやすく接続する汎用的かつ実用的な定式化モデルを再構築・体系化し，それらを構成する離散構造処理，制約充足，列挙，離散最適化，量子計算理論など，日本が強みを持つ分野を中心としたアルゴリズムの理論と技法の研究を推進し，革新的アルゴリズム基盤として発展させることを目指している．本講演では研究領域の概要と，今後の研究活動について紹介する．

【略歴】1988年 京大・情報工卒，1990同大学院修士，1995同博士（社会人）了．博士（工学）．1990～2004年NTT研究所に勤務．1997年（1年間）米国スタンフォード大客員研究員．2004年 北大・情報科学研究科・助教授，2010年 同教授．2018年より現職．大規模離散構造データの表現と演算処理アルゴリズムの研究・教育に従事．2009～2015年 JST ERATO湊プロジェクト研究総括．2017年より日本学術会議連携会員．2020年より科研・学変（A）「アルゴリズム基盤」領域代表．2018～2019年および2021年より本会理事．本会シニア会員，電子情報通信学会シニア会員，IEEEシニア会員，人工知能学会，日本計算機統計学会 各会員．

【講演概要】情報科学では多くの問題が研究されてきているが，その問いの多くは40年以上前 に設定された概念や価値観，つまり精度，制約，コストなどに基づいて設定されている．しかし，SNSの登場による新たなコミュニケーションのあり方や，環境指向，多様性の尊重などの近年の新たな社会価値（規範）は，問題解決に取り組む際の取り組み方や着目点を大きく変化させるものである．この変化に十分な注意を向けないなら，情報科学が取り組む問題は社会で取り組まれる課題や方法論から乖離してしまいかねないだろう．したがって，このような社会の価値観や方法論に沿った問いを，情報科学は新しく立て直さなければならない．このような中で，AFSA-A01問題定式化班では，人文社会学，デザインなどの視点と知見を取り入れ，新しい価値観と概念に基づく新しい問題群の記述を行っている．本講演では，この活動の状況と現在までに得られた成果を紹介する．

【略歴】本会正会員．1998年東京工業大学システム科学専攻博士（理学）を取得．同年同経営工学専攻助手着任，2001年国立情報学研究所助教授着任．現在は教授．専門はアルゴリズム理論とその応用，特に離散・列挙・組合せ最適化，データマイニング・データ解析での大規模高速計算．2010年文部科学大臣表彰若手科学者賞受賞．

【講演概要】本企画シンポジウムでは，アルゴリズムに関連する幅広い情報科学分野の研究者・技術者の方々に，AFSAプロジェクトへの理解を深めてもらい，興味を持ってもらうことを目的として，AFSAプロジェクト関係者6名による最新の研究テーマに関するポスターセッション形式での講演とディスカッションを行います．まず各テーマについて2分間の全体向け講演（フラッシュトーク）を行った後，対面とオンラインと組み合わせたハイブリッド形式での個別討論（ポスターセッション）を試みたいと思います．新しい討論形式での活発な意見交換を期待しています．

【略歴】1988年 京大・情報工卒，1990同大学院修士，1995同博士（社会人）了．博士（工学）．1990～2004年NTT研究所に勤務．1997年（1年間）米国スタンフォード大客員研究員．2004年 北大・情報科学研究科・助教授，2010年 同教授．2018年より現職．大規模離散構造データの表現と演算処理アルゴリズムの研究・教育に従事．2009～2015年 JST ERATO湊プロジェクト研究総括．2017年より日本学術会議連携会員．2020年より科研・学変（A）「アルゴリズム基盤」領域代表．2018～2019年および2021年より本会理事．本会シニア会員，電子情報通信学会シニア会員，IEEEシニア会員，人工知能学会，日本計算機統計学会 各会員．

【講演概要】ウエブ情報学の一分野であるソーシャルメディア解析は，主としてオンライン上で集められた大量の言葉の定量的な分析を通じて，書き手の行動や心的状態を推し量る学問分野である．一方，文学もまた，作品の言葉を通じて，書き手の意図や心的状態を知ることを目的とする．両分野とも，言葉を通じて人間に関する真理を知るという目的に向かうものの交わり合うことはほとんどない．本発表では，文学という学問領域の暗黙知を通じて，両分野が有機的に交わり合う可能性を考えてみたい．

【講演概要】混雑ゲームとは人々が自分勝手に資源を選ぶ状況をモデル化した非協力ゲームで，その均衡状態は人々が各々自らのコストを下げようとした際の資源の選び方をシミュレートしているものだと思える．従って，ネットワークなどのインフラを設計する立場から見れば，均衡状態における社会コストが低くなることが望ましい．本研究では，均衡状態における社会コストを下げる良いパラメータ，すなわち社会デザインを求める問題で，特に資源の組合せを選ぶ現実的かつ複雑な設定に対し，実用的な新手法を提案した．手法は新たに開発した微分可能最適化法とゼロサプレス型二分決定グラフ（ZDD）とよばれるデータ構造の組合せであり，従来研究と比べより広範な問題に適用可能である．

【講演概要】Recently, motivated by the importance of understanding the relationship between solutions of a problem, reconfiguration problems have been extensively studied. In a reconfiguration problem, a primary question is whether one can transform an initial solution into a target one via a sequence of solutions (called a reconfiguration sequence). Each intermediate member of the sequence must be obtained from its predecessor by applying a given reconfiguration rule exactly once. In a reconfiguration problem, a forbidden structure is the terminology used to indicate a part of each configuration having certain properties that obstruct the existence of a reconfiguration sequence. In this poster, we present some examples from our past and current research to illustrate the importance of forbidden structures in designing polynomial-time algorithms for solving reconfiguration problems. Along the way, we include some interesting open problems.

【講演概要】無向グラフGに対するf-耐故障連結性ラベリングとは，Gの頂点集合および辺集合に対するラベル付けであり，任意の2頂点s,t，および高々f個の辺集合Fに対して，Gより辺集合Fを取り除いたグラフにおいてs-t間が連結であるかどうかをs,tおよびFに付与されているラベルのみから判定することが可能であるような（分散型）データ構造の一種である．本発表では，f-耐故障連結性ラベルを構成する決定性多項式時間アルゴリズムを提案する．発表者の知る限り，このアルゴリズムは一般のグラフに対して同ラベルを構成する世界初の決定性アルゴリズムである．

【講演概要】グラフ状態はグラフで表現される量子状態であり，様々な量子情報処理に用いられる．グラフ状態は局所クリフォード演算とCZ演算を用いることで生成することができる．本研究では，局所クリフォード演算とできるだけ少ない回数のCZ演算を用いることでグラフ状態を生成する方法について研究した．コンピュータを使った探索によって10頂点以下のすべてのグラフ状態について生成に必要なCZ演算の最小回数を計算した．その結果，従来手法に比べて少ない回数のCZ演算で生成できるグラフ状態を発見した．また，n 頂点のサイクルグラフに対応するグラフ状態は 5 ≦ n ≦ 10 のときに，n 回のCZ演算を必要とすることが分かった．局所クリフォード演算について不変な性質を考察することによって，一般に n ≧ 5 頂点のサイクルグラフに対応するグラフ状態はn 回のCZ演算を必要とすることを証明した．その他にも局所クリフォード演算で不変な性質をいくつか明らかにした．

【講演概要】グラフの連結性はグラフの基礎的な性質であり，列挙アルゴリズム分野でも様々な連結性の制約に対し，効率良い列挙アルゴリズムが開発されている．特に，極小な全域連結部分グラフである全域木の列挙は古くから研究されており，この問題はならし定数時間で列挙できることが知られている．一方，グラフの2頂点連結な極小全域部分グラフについても効率良い列挙アルゴリズムは知られているが，このアルゴリズムの時間計算量は増分多項式時間である．つまり，これらの問題は時間計算量の観点ではならし定数時間と増分多項式時間といったある意味で指数的な計算時間のギャップが存在する．本研究では連結性に関するこれらの列挙問題に対し，多項式遅延で解ける範囲を明らかにするため，平面グラフに対する極小全域 k 辺連結部分グラフの列挙に取り組み，この問題が多項式遅延で列挙できることを明らかにした．