河東先生や立川先生にならって，論文の背景についてコメントしています．
Coming soon.
森先生のもとで量子アルゴリズムを研究するRAとして雇っていただいていたが，最初やろうとしていたことがあまり上手くいかず，自分の興味を持った量子のクエリ計算量の計算量を考えてみることに．森先生がパラメータ化計算量を量子クエリの設定で考えられないかと言うので，(古典の)FPTについて色々サーベイしてみることに．そして，$k$-vertex coverに対するほとんど知られていない$O(3^k n)$時間のアルゴリズム([Papadimitriou-Yannakakis '96]が発見した極大マッチングを使ったアルゴリズム)から着想を得て, $k$-vertex coverが$O(kn)$量子クエリで(隣接行列モデルの設定で)解けることに気が付く．ただ，下界を考えると$O(\sqrt{k} n)$クエリとなりギャップがあった．その後，夜道を歩いている時に，FPTの教科書でみたkernelizationのreduction ruleを極大マッチングの端点のみに適用するというアイデアを思いつく．これで，$k$が小さい時には上界と下界を一致させることができた．この半年後くらいに，量子クエリの設定と分散計算の設定って近いんだよなと思い，$k$-vertex coverのアイデアを分散計算にも適用できないかなと思いつく．ちょっと調べると，実は近いことはやられていることがわかり，論文を読んでみると，逆に，分散の$k$-matchingのアルゴリズムが量子のクエリの設定に使えるのではと思いつく．それでこの二つを組合せて論文化した．
ICALP'23で自分の発表のちょうど次の発表が，特殊なマトロイド制約で劣モジュラ関数最大化を高速化するという論文についてだった．それを聞いている時に，一般のマトロイドでオラクルの設定で，(最近のマトロイド交叉の高速化に使われている)二分探索のテクニックを使って高速化できないだろうかと思った．帰って，(マトロイド制約での劣モジュラ最大化のアルゴリズムの肝となる) swap roundingの論文についてゼミで小林先生と話している時に，小林先生が(マトロイド交叉のアルゴリズムに用いる)交換可能グラフのような補助グラフの中で有向サイクルを高速に見つけることができれば，丸めアルゴリズムが高速化できてことに気が付く．同じ週の週末に，実家のこたつで，清水先生のブログに載っているアルゴリズムのことをふと思い出し，そこから着想を得て，$\tilde{O}(\sqrt{r})$個の頂点をグラフからサンプルするアルゴリズムを思いつく．次の週に小林先生に話し，アルゴリズムに微妙に誤りはあったが，ほぼ同じアイデアでうまく修正することができ，論文化できた．これがICALP'24に通ったのもめでたい．あとにでた論文で計算量は抜かれたが，そのあとに出た現状最速の論文では我々のアルゴリズムを使用している．(連続最適化の部分が高速化された．)
(競プロ出身なので，)アルゴリズムの高速化をやりたいと思っていたので，興味があったマトロイド交叉の最近の高速化のブレイクスルーの論文をいくつか読んでみることにした．それで何をしようかと思った時，マトロイド交叉の長らく最速だったCunninghamの論文が，マトロイド分割に対しても最速のアルゴリズムを提案していたので，安直だが，マトロイド分割も(最近のマトロイド交叉の高速化に使われている)二分探索のテクニックを使って高速化できないだろうかと思う．ちょっと考えると，マトロイドの個数$k$が小さい時には簡単に高速化できることが分かったが，流石に簡単すぎるのでこれでは論文にはできないなとなる．そこで，$k$が大きい時も高速化できないだろうかと考えることにする．考え始めてから1ヶ月ほどして，Cunninghamの論文で肝となっている補題(私の論文のarXiv版ではLemma 2.10)をうまく使うと，平方分割的なことができることに気が付く．このアイデアでかなり簡単に$k$が大きい場合でも改善できることが確認でき，その後，もう少し解析を精緻化させて論文化した．コルテとフィーゲンによる組合せ最適化の有名な教科書の最初の方に組合せ最適化の重要な問題として80問ほど載っている中の一つの問題に対して，最速のアルゴリズムを与えられたのはめちゃくちゃ嬉しいし，ICALPに単著を通せたのもとても嬉しい．
卒論の代わりとして，小林先生がやっていたshortest disjoint pathsの研究を少しすることに．BjörklundとHusfeldtの論文から始まったいくつかの関連研究から膨らませて研究することになった．この論文の大部分は小林先生のおかげなので，小林先生に感謝したい．