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

P 类中的参数化复杂度层次结构

• 批准号: 19J12876
• 负责人: 清水 伸高
• 金额: $ 0.58万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-25 至 2021-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19J12876/
• 关键词: ランダムグラフ; 平均計算量; 合意モデル; ランダムウォーク; 計算量

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

我们得到了与图上的随机性相关的三个结果。第一个结果涉及随机图的计算复杂度。对于固定大小的完全二分图的子图计数问题，我们解决了固定大小的完全二分图的子图计数问题在强指数时间假设 (SETH) 下，我们给出了由 生成的精化参数化平均复杂度的下界。 （SODA）。第二个结果涉及图上的共识模型。在共识模型研究的背景下，大多数论文都专注于特定模型并讨论其属性，但本研究提出了一个通用共识模型类，其中包括许多共识模型到目前为止已经进行了研究，并证明属于该类的任何共识模型都可以在扩展图上快速达成共识（以对数轮次），该结果已在 2020 年的国际学术讨论会上提出。自动机、语言和编程（ICALP）。最终结果涉及动态图上的随机游走。随机游走由于其简单性而广泛应用于网络分析，但它们经常用于现实世界中出现的网络结构。图的变化随时间的推移而变化。现有一些关于动态图上随机游走行为的研究，但大多数都考虑了图中顶点数量不变的设置。在这项研究中，我们提出了一个讨论图上随机游动的框架，其中顶点数量随着时间的推移而增加，并阐明了其属性。这项工作在离散算法研讨会（SODA）上被接受。

项目成果

Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models

随机块模型上的最佳二选一和最佳三选一的相变

• DOI: 10.1002/rsa.20992
• 发表时间: 2021
• 期刊: Random Structures & Algorithms
• 影响因子: 1
• 作者: Shimizu Nobutaka;Shiraga Takeharu
• 通讯作者: Shiraga Takeharu

The Average Distance and the Diameter of Dense Random Regular Graphs

稠密随机正则图的平均距离和直径

• DOI: 10.37236/8705
• 发表时间: 2020
• 期刊: The Electronic Journal of Combinatorics
• 作者: Shimizu Nobutaka;Shiraga Takeharu;Shimizu Nobutaka
• 通讯作者: Shimizu Nobutaka

How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?

在适度增加顶点数量的网络中，随机游走会丢失多少个顶点？

• DOI: 10.1137/1.9781611976465.8
• 发表时间: 2021
• 期刊: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
• 作者: Kijima Shuji;Shimizu Nobutaka;Shiraga Takeharu
• 通讯作者: Shiraga Takeharu

Quasi-Majority Functional Voting on Expander Graphs

扩展图上的准多数功能投票

• 发表时间: 2020
• 作者: Shuji Kijima;Nobutaka Shimizu;and Takeharu Shiraga;Nobutaka Shimizu and Takeharu Shiraga
• 通讯作者: Nobutaka Shimizu and Takeharu Shiraga

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

• DOI: 10.1137/1.9781611976465.140
• 发表时间: 2020-10
• 作者: Shuichi Hirahara;Nobutaka Shimizu