研究室紹介OPAL-RING
伊藤（大） 研究室

離散アルゴリズムに関しては、数多くの国際ジャーナル（論文誌）や国際会議で論文を発表して高い評価を得ており、当研究室は世界でもトップクラスだと自負している。
また、離散アルゴリズムや離散数学の世界最高の研究者たちとの人脈を築いていることが大きなアドバンテージになっている。いろいろな国際会議に出席したり、それぞれの大学を訪問することで世界中のトップの研究者と交流できるので、世界の最先端の情報が入ってくる。さらに、研究者同士の共同研究で新しい課題にチャレンジできることも、当研究室の研究を活気づけている。
企業との共同研究でオンラインアルゴリズムを応用（グリーンアルゴリズム）
企業との共同研究も積極的に行っている。例えば、パナソニックとオンラインアルゴリズムの共同研究を行った。具体的には、コピー機やコンピュータなどの待機状態（スリープモード）を制御して、より節電するためのエコ家電のグリーンアルゴリズムだ。
既存の制御理論では、人がいつ使ったかを学習して制御するが、伊藤は離散アルゴリズムの一つであるオンラインアルゴリズムを利用した。このアルゴリズムでは、情報がつぎつぎに与えられてその都度自律的に判断していく。そして、未来の情報が予測できる万能の「神」が制御した場合のコストと比較して、最悪でも何倍のコストで納められるか（これを競合比と呼ぶ）をなるべく少なくすることが目標となる。
この問題に対する既存研究における競合比は2で、それが「最適」であることが証明されていた。しかし、この「最適」アルゴリズムを使うと、少ない数の客がランダムに到着するという本来制御が楽な系であっても、最悪に備えるため常に2倍のコストを掛け続けることになってしまうという明らかな弱点があった。
当研究室では、一回無駄な待機を行ったら次回には切るタイミングを早めて、待機が無駄でなかったら元に戻すという手法をとった。そして、肝心の競合比の上限をεだけ緩め「2～2＋εの差を気にしない(don't care)」とすることによって、ランダムな到着の場合は平均的な競合比が1に近く、そして最悪時の競合比も理論的に最適であるアルゴリズムを与えた。
この成果は2011年にドイツで行われた国際会議で発表し、高い評価を受けた。このように、当研究室のアルゴリズムを使うことで、さまざまな現実問題解決に応用することができる。

理論研究者にとって一番の生き甲斐は、未解決問題への挑戦だ。伊藤の参加する新学術領域研究「多面的アプローチの統合による計算限界の解明（代表者：渡辺治 東工大教授）」が2012年より始まり、現代数学の7大未解決問題の一つ「P vs. NP」（解の発見 対 解の検証）に挑んでいるが、文部科学省の支援を得てメンバーの意気込みも高く、この難攻不落の難問への鍵が得られるかもしれないと期待している。

ビッグデータ社会におけるアルゴリズムは、定数時間を中心とした劣線形時間アルゴリズムが基本となるという、伊藤の提案した「劣線形時間パラダイム」をコンセプトとした研究プロジェクトJST CREST「ビッグデータ時代に向けた革新的アルゴリズム基盤」が2014年より発足した。ビッグデータのための理論基盤の構築に向けて新たな挑戦が始まっている。