執筆した論文で，やろうと思ったきっかけや，アイデアを思いついた背景などで面白いものがあれば，コメントとして残しておきたいと思う．
マトロイド交叉問題のrandom-orderでのstreamingアルゴリズムの論文 [Huang-Sellier'24]を読んで，自分もマトロイド交叉問題に関するstreamingアルゴリズムについて何かできないかと考え始めた．マッチングに対する最も初期のsemi-streamingアルゴリズムの論文 [FKMSZ'05]を読んでる際に，マッチングだと，長さ3のaugmenting pathをほとんど見つけ切れば，$(2/3-\varepsilon)$-近似が達成でき，これは簡単にstreamingで実装できることを知った．その後，同様のアイデアで，最近のマトロイド交叉問題に対するaugmenting setsを使った$(1- \varepsilon)$-近似アルゴリズム [Blikstad'21]を途中($1/\varepsilon$ rounds)で止めるだけで，$(2/3-\varepsilon)$-近似が達成できることに気が付いた．また，これは，streamingだけではなく，offlineの設定でも，ほぼ線形回の独立性オラクルへのクエリで$(2/3-\varepsilon)$-近似が達成できているという面白い結果を意味していることに気がついた．
まず最初に，$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のアルゴリズムをベースに，$k$-matchingに対する量子クエリアルゴリズムを設計した．それでこの二つを組合せて論文化した．
ICALP'23で自分の発表のちょうど次の発表が，特殊なマトロイド制約の劣モジュラ関数最大化問題を高速化するという論文についてだった．それを聞いた際に，一般のマトロイドでオラクルの設定で，(最近のマトロイド交叉の高速化に使われている)二分探索のテクニックを使って高速化できないだろうかと思った．その後，(マトロイド制約での劣モジュラ最大化のアルゴリズムの肝となる) swap roundingの論文についてゼミで小林先生と話している時に，小林先生が(マトロイド交叉のアルゴリズムに用いる)交換可能グラフのような補助グラフの中で有向サイクルを高速に見つけることができれば，丸めアルゴリズムが高速化できてことに気が付いた．その週末，清水先生のブログに載っているアルゴリズムのことをふと思い出し，そこから着想を得て，$\tilde{O}(\sqrt{r})$個の頂点をグラフからサンプルすることで，高速なアルゴリズムを設計できることを思いついた．後の論文で計算量は抜かれたが，そのあとに出た現状最速の論文では我々のアルゴリズムを使用している．(連続最適化の部分が高速化された．)
(競プロ出身なので，)アルゴリズムの高速化をやりたいと思っていたので，興味があったマトロイド交叉の最近の高速化の読んでみることにした．それで何をしようかと思った時，マトロイド交叉の長らく最速だったCunninghamの論文が，マトロイド分割に対しても最速のアルゴリズムを提案していたので，マトロイド分割に対しても(最近のマトロイド交叉の高速化に使われている)二分探索のテクニックを使って高速化できないだろうかと思った．ちょっと考えると，非常に簡単に高速化できることが分かった．しかしながら，マトロイドの個数$k$が大きい時$(k = \Omega(n))$は，Cunninghamの論文よりも速いアルゴリズムを与えられのは容易ではなかった．そこで，$k$が大きい時も高速化できないだろうかと考えることにする．考え始めてから1ヶ月ほどして，Cunninghamの論文で肝となっている補題(私の論文のarXiv版ではLemma 2.10)をうまく使うと，"平方分割"的なことができることに気が付く．このアイデアでかなり簡単に$k$が大きい場合でも改善できることが確認でき，その後，もう少し解析を精緻化させて論文化した． Korte-Vygenによる組合せ最適化の有名な教科書に組合せ最適化の重要な問題として80問ほど載っている中の一つの問題に対して，最速のアルゴリズムを与えられたのは喜ばしい．