2014年になってからだいぶ経ちましたが2013年の進捗を振り返ろうかと思います．
プログラミングコンテスト絡みのことはTopCoder部の方に書いたのでそっちを御覧ください．
卒論の成果をジャーナルに出した
Kusumoto Mitsuru, Yuichi Yoshida, and Hiro Ito. Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs. (IJNC'13)
卒論の成果をIJNCというジャーナルに投稿して，何度かの修正を経て収録されました．ここに投稿する前に ICNC (dblp) という会議で発表したのですが，これはそのジャーナル版にあたります．
内容としては，最大重み有向森問題という有向グラフの最適化問題があるのですが，その問題の最適値の値を，グラフのごく一部分だけを見て近似的に計算するアルゴリズムを提案した，というものです．最大重み有向森は最小有向木問題と等価(互いに多項式時間帰着可能)な問題として知られていて，組合せ最適化とかにも載っています．
この論文はここに落ち着くまでにいくつか別の国際会議に出して落ちるといったことを繰り返していて，割と色々な場所を彷徨っていました．中には結構惜しいところ(というか半ば理不尽っぽい感じのレビュー)でRejectを受けたりしたものもあって悔しい思いをしたというのが正直なところです．今回収録されてとりあえず成仏された感じになりました．
ラボ輪講
研究関係のこと(理論計算機科学とか離散数学)でもっと体系的な知識を付けたいと思ったので，4月から新B4生達も交えてラボ内で輪講をしました．とりあえず読んだのは N.Alon と H.Spencer の Probabilistic Method と，D.Spielman の Spectral Graph Theory の2つです．
Probabilistic Method は確率事象を考えることによって存在性を示したり何かの上界や下界を証明する手法のことです．ラムゼー理論のような，普通にやったらどうやって解析すればいいのかよくわからない感じの問題が多く扱われています．できるだけ読み飛ばさないスタイルで，しかも結構ゆっくりと進めたので，1年で読むことができたのは本の30%くらいでした．それでも解析のための様々なテクニックを丁寧に見ることができたのは良かったかもしれません．(実際の場面で活用できるかというとそれはまた別の話かもしれませんが．)
Spectral Graph Theory はグラフを隣接行列やラプラシアンの固有値の観点から解析する手法で，いろいろなところに応用があります．ここでやったことは9月のPFIセミナーの発表資料にひと通りまとめています．普通にスペクトルグラフについて詳しくなれたほかに以前と比べて線形代数に強くなった(気がする)ので学べたことは多いと思います．ひとまず興味のあるところは読み終えたので，せっかくなので次はスペクトルグラフのテクニックを使った論文を読んでみよう，みたいになっています．
IJCAI参加，発表
Danushka Bollegala, Mitsuru Kusumoto, Yuichi Yoshida, and Ken-ichi Kawarabayashi, Mining for Analogous Tuples from an Entity-Relation Graph. (IJCAI'13)
僕は2012年の後期から河原林巨大グラフプロジェクトでRAをやっているのですが，そこで東大のダヌシカ先生たちと共同で研究をして投稿したところ，IJCAI(AI系のトップ会議)に採択されたので発表に行ってきました．
僕自身は主にアルゴリズムの実装と実験を担当して second author という位置づけだったのですが，first author のダヌシカ先生が別件で会議に出られないとのことだったので僕が行って発表することになりました．
開催場所は北京でした．噂に聞いていたとおり空気が悪かったので呼吸に気をつけながら滞在しました．
AIは専門外の分野だったので発表を聞いてもわからないことも多かった(というかそもそもAI自体が様々な分野の集合体なので…)のですがどういう問題が重要とされているかとかどういう手法がメジャーなのかとかはなんとなく分かった気がします．
現在，今後
修論で成果が出ていたり，他にも何かしているような気がするのでそれらを何らかの形にして publish したいです．
