理論計算機科学

分散システムを中心とした、様々な計算モデルの上でのアルゴリズム設計手法並びに計算限界解明の研究を行っています。近年は計算機の能力向上が著しく、ややもするとどんな複雑な問題でもコンピュータがたちどころに答えを出せるような幻想を抱いてしまいますが、実は最善の答えを高速に計算できるような手法(アルゴリズム)が知られている問題というのは実世界における課題のほんの一握りであり「いったいどのような問題であれば計算機は効率よく答えを出せるのか」という根源的な問いに対する解答の大部分はいまだに闇の中にあります。アルゴリズム理論および計算量理論の研究を通じて、様々な問題の本質的な困難性を理解するとともに、その知見を活かした優れたアルゴリズムの設計を目指して研究しています。