ダグシュトゥールの1週間

Exact Complexity of NP-hard Problems というワークショップにいっていました．いわゆるSTOC，FOCS，SODA，ICALP級の発表が目白押しで，非常に楽しく勉強になりました．私の出した問題も面白いといってくれる人が多く，うれしかったです．

2年前にも同じテーマのワークショップに参加したのですが，そのときと比べて分野の急速な発展を見ることができました．包除原理を使うことは当たり前となり，代数を用いたアルゴリズムによって計算量を改善できる，といった方向も出てきました．一方，アルゴリズムの限界を見極める方向では，問題の間の還元に関する研究が精力的に行われて，問題どうしの難しさに関する理解が深まっています．