本研究では、基礎的なアルゴリズムに関する研究を行い、成果をあげた。以下に主要な２点を挙げる。
グラフの連結度を求める問題は、東西冷戦時代（つまり1950 年代）より組合せ最適化における中心的課題の一つである。以下の論文では、辺連結度に関して、初の「決定的」な「ほぼ」線形アルゴリズムを与えた。辺連結度に関する「非決定的」な「ほぼ」線形アルゴリズムは、Karger により2000 年に開発されていたが、「決定的」アルゴリズムは長年未解決であった。本論文はその最終的な解決を与えている。本論文は、コンピューターサイエンス分野の最高峰の国際学術雑誌 Journal of the ACM（ J. ACM） に掲載されている。またグラフの連結度を求める問題は、グラフの最小カットを求める問題に相当する。この最小カットを拡張するk-カット問題は、NP困難問題であることが知られているが、既存の近似アルゴリズムを大幅に更新した。
バンディット問題は、現在機械学習分野における一大分野であり、最悪ケースにおけるリグレット解析、および計算量の解析が主要課題である。またバンディット問題の中にも、組合せ最適化問題、オンライン線形計画化問題など、数多くのバリエーションがある。本研究では、１．バンディット組合せ的最適化問題に対して、最悪ケースにおけるリグレット損失の下界を改善。２．バンディットフィードバックを持つオンライン線形最適化問題に対して、オフライン線形最適化問題を解くオラクルを仮定したもとで、劣線形リグレットを達成しつつ効率的な（つまりオラクル呼び出し回数が少ない）アルゴリズムを与えた。３．バンディット問題のオンラインポートフォリオ版に対しても、最善のリグレットバウンドを与えた。