2017年9月30日土曜日

単著論文がSODAに通りました

The Diameter of Dense Random Regular Graphs
という単著の論文がSODA18に採択されました.

SODAは Symposium on Discrete Algorithms という理論的な国際会議で, コンピュータ科学において「トップカンファレンス」と呼ばれるもので, なかなか通すのが難しいと言われています. 今年のSODA17には通した日本人が1,2人しかいなかったと記憶しています. 今年はバルセロナでの開催でしたが, 来年のSODAはニューオリンズです. 他にもFOCS, STOCなどが有名です.

通した論文の内容はランダム正則グラフの直径についてのものです. ランダム正則グラフは次数が定数の場合は直径が漸近的(頂点数→無限)に"最適" (i.e. Moore Boundから得られる直径の理論下界との比が1に収束)で, HPCのネットワークトポロジーとしても有用であることが知られています. しかし次数が頂点数とともに増加する場合はその直径がどうなるかはexplicitには知られていませんでした. (実際にはMoore Bound と最近発表された定理を拾ってくるとだいたいのケースでは上界と下界が得られます). 今回の論文はそのようなランダム正則グラフの直径について, 次数dが $d=\beta \cdot n^{\alpha}$ ($n$は頂点数) の場合だとその直径が $\lfloor \alpha^{-1} \rfloor + 1$ となることを証明しました (研究の本質的な点は, 上記の次数を持つランダム正則グラフに対してMoore Boundから得られる下界と上述の定理から得られる上界の間のギャップに関する問題を解決したという点にあります)

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...