クラスＰにおけるパラメタ化計算量階層

グラフ上のランダムネスに関する三つの業績を得た.一つ目の成果はランダムグラフの計算量に関するものである. 固定サイズの完全二部グラフの部分グラフ数え上げ問題に対し, 入力がランダム二部グラフによって生成される時の精緻なパラメタ化平均計算量の下界を強指数時間仮説(SETH)の下で与えた. 本成果は理論計算機科学のトップ会議Symposium on Discrete Algorithms (SODA)に採択された.二つ目の成果はグラフ上の合意モデルに関するものである. 合意モデル研究の文脈では特定のモデルを対象としてその性質を議論する論文がほとんどであるが, 本研究ではこれまで研究されてきた多くの合意モデルを含む一般的な合意モデルのクラスを提案し, そのクラスに属する任意の合意モデルがエキスパンダーグラフ上で高速に(対数ラウンドで)合意に至ることを証明した. 本成果は2020年にInternational Colloquium on Automata, Languages and Programming (ICALP) に採択された.最後の成果は動的グラフ上のランダムウォークに関するものである. ランダムウォークはその単純さからネットワーク解析などで広く用いられるが, 実世界に現れるネットワークはその構造が時間とともに変動する. 動的グラフ上のランダムウォークの振る舞いに関する既存研究は幾つか知られているが, それらのほとんどは考えるグラフの頂点数が変動しないという設定を考えていた. 本研究では頂点数が時間とともに増えていくグラフ上のランダムウォークを議論する枠組みを提案し, その性質を明らかにした. 本成果はSymposium on Discrete Algorithms (SODA)に採択された.

グラフ上のランダムネスに関する三つの業績を得た.一つ目の成果はランダムグラフの計算量に関するものである. 固定サイズの完全二部グラフの部分グラフ数え上げ問題に対し, 入力がランダム二部グラフによって生成される時の精緻なパラメタ化平均計算量の下界を強指数時間仮説(SETH)の下で与えた. 本成果は理論計算機科学のトップ会議Symposium on Discrete Algorithms (SODA)に採択された.二つ目の成果はグラフ上の合意モデルに関するものである. 合意モデル研究の文脈では特定のモデルを対象としてその性質を議論する論文がほとんどであるが, 本研究ではこれまで研究されてきた多くの合意モデルを含む一般的な合意モデルのクラスを提案し, そのクラスに属する任意の合意モデルがエキスパンダーグラフ上で高速に(対数ラウンドで)合意に至ることを証明した. 本成果は2020年にInternational Colloquium on Automata, Languages and Programming (ICALP) に採択された.最後の成果は動的グラフ上のランダムウォークに関するものである. ランダムウォークはその単純さからネットワーク解析などで広く用いられるが, 実世界に現れるネットワークはその構造が時間とともに変動する. 動的グラフ上のランダムウォークの振る舞いに関する既存研究は幾つか知られているが, それらのほとんどは考えるグラフの頂点数が変動しないという設定を考えていた. 本研究では頂点数が時間とともに増えていくグラフ上のランダムウォークを議論する枠組みを提案し, その性質を明らかにした. 本成果はSymposium on Discrete Algorithms (SODA)に採択された.