The 22nd International Symposium on Algorithms and Computation

情報セキュリティ研究室 > 学会/セミナー報告 > ISAAC 2011
ISAAC 2011 参加報告

【会議名】The 22nd International Symposium on Algorithms and Computation (ISAAC 2011)
【開催日時】2011年12月5日 -- 12月8日
【場所】ワークピア横浜 神奈川県横浜市
【報告者】安永研究員


  12月5日は、ISAAC の開催に先駆けて、東京工業大学の渡辺治教授が代表を務める Golobal COE Project CompView の最終ワークショップが開催されました。
  CompView とは、「計算」というものを中心にして様々な物事を眺めてみようという考え方です。
 例えば、暗号理論において、公開鍵暗号は、敵対者の計算能力にはある程度の限界があると仮定することで初めて達成可能な概念です。
 つまり、敵対者も計算を行うという視点を取り入れることで、生まれてきた概念であり、暗号理論は正に CompView の代表的な事例です。
 本年度は、その CompView プロジェクトの最終年度であり、その最終ワークショップが ISAAC 2011 と連続して開催されることになりました。
 最終ワークショップでは、日本 IBM 副社長の岩野和生氏、マイクロソフトリサーチの Ravi Kannan 氏の招待講演、
 GCOE プロジェクトに関わった若手研究者の発表として、東京工業大学の下川辺隆史さん、大阪大学の河原吉伸助教による発表、
 および、GCOE プロジェクトに関わった RA の学生によるポスター発表が行われました。
 12月6日から8日は ISAAC 2011 の開催であり、テクニカルプログラムに加え、
 プリンストン大学の Sanjeev Arora 教授、カールスルーエ技術研究所の Dorothea Wagner 教授の招待講演が行われました。
 参加者数は、私の目測で150名程度はいるように見えました。
 ISAAC は、アルゴリズムと計算に関するシンポジウムであり、アルゴリズムおよび計算量理論に関わる国内研究者の多くが参加されているという印象を受けました。

 以下、いくつかの発表についての所感です。

----------------------------------------------------------------------------
Kazuo Iwano, Smarter Planet Initiative - Now and Next
----------------------------------------------------------------------------
情報システムを利用して社会システムの問題解決を行うことに関する IBM の取り組みである 
Smarter Planet について事例を交えながら説明された。
これらの実現においてもセキュリティは高コストになりがちだが重要であると説明されていた。
特に、どのデータをどのクラウドが計算したかということをトレースできる仕組みが重要だと強調されていた。
理論計算機科学の立場として、どのような貢献が可能かという質問に対して、
分散メモリ環境に対応する計算モデルの構築、計算機と計算機によるコラボレーション技術の開発、などを挙げられていた。

----------------------------------------------------------------------------
Dorothea Wagner, Algorithm Engineering for Route Planning: An Update
----------------------------------------------------------------------------
経路計画における計算、要は最短経路問題について、初期の研究から最新の研究までをサーベイするという話であった。
本テーマに関する講演は初めてだったため、詳細な部分はついていけなかったが、ざっと歴史的な流れを説明すると、
まず、最短経路問題に対しては、Dijkstra 法が最も基本的な方法として存在する。
それを改良するという動機のもと、1999年頃までは、最悪ケースに対する実行時間の改良に関する研究が発展し、
A*アルゴリズムなどが開発された。その後、2005年頃までに、goal-directed と hierarchical approach という2つのアプローチが登場し、
最近では、時間依存だったり、複数の指標がある場合など、より複雑な場合を考えようになっている。
そして、考える問題が複雑になると、理論よりも現実が先行し、あるアルゴリズムがなぜうまく働いているかということを
理論が後追いで保証するという方向の研究も進んでいるということでした。

----------------------------------------------------------------------------------------------------------
Sanjee v Arora, Semidefinite programming and prroimation algorithms for np-hard problems: a tour d'horiozn
----------------------------------------------------------------------------------------------------------
半正定値計画問題について、その動機から最新の研究トピックについてのお話でした。
私自身は、あまり予備知識がなく、比較的早い段階で内容を追うことができなくなってしまいました。

ページトップへ戻る

Copyright © 2011 Institute of Systems, Information Technologies and Nanotechnologies. All Rights Reserved.