渡辺 治 （わたなべ おさむ / Osamu WATANABE）

EVENT MESSAGE OK!!

Mail: watanabe-at-is.titech.ac.jp
Click here for Watanabe's home page (English).

１．自己紹介

研究について

計算の複雑さやアルゴリズムの設計と解析に関する理論全般に興味を持って研究しています． 最近では，とくにランダムに興味があり， アルゴリズムや計算論的な立場から， ランダムネスの様々な側面について研究しています．

最近の話題（10/25/07 update）

• 博士学生募集＆ポスドク（６つのテーマで）募集
  文部科学省グローバルＣＯＥプログラムの１つとして， ＧＣＯＥ「計算世界観の深化と展開」（拠点リーダー：渡辺治）が 2007年8月よりスタートしました．

  詳しくは拠点ホームページをご覧下さい．

  • 人間が解析できることは， 原理的にはコンピュータ上で実現できる「計算」と見なすことができます． 計算世界観 (CompView) ＧＣＯＥでは， 科学の対象となる様々な現象を計算を中心に見直すことにより， 新しい科学の手法を開拓していくことを目指します．
  • グローバルＣＯＥでは 各拠点に博士課程学生の教育の充実を目指すことが求められています． 本拠点でも， 「計算世界観」の実践者たる博士の教育を目指し， 研究インターンシップやＲＡ経費による支援を初め 様々な取り組みを計画しています． 上記のウェブページをご覧の上，是非，応募してください．
  
  
• 数独の解盤面すべてに番号（インデックス）を与えることに成功しました！ 東工大のスパコン TSUBAME のほんの一部 (60/10000) を使って４時間の計算でした． 数独インデックスのページを見てください． 皆さんのお手持ちの数独の番号を約１０秒で計算してくれます！

少し前（２００６年）の話題から

• ランダムについての研究を紹介する特集を企画し， 数理科学９月号として発刊しました． ランダムネスの様々な側面を解説しています： 中身をちょっとだけご紹介→pdf file．
• 「ブースティング --- 学習アルゴリズムの設計技法」 （金森，畑埜，渡辺著，森北出版）を８月に発行しました． ブースティングに特化した，かなり専門的な話ですが， アルゴリズムと統計の両方の側面からブースティングを詳細に述べています： 表紙， 中身をちょっとだけご紹介→pdf file．

講演会・セミナーなどの案内

• Complexity Seminar： 計算の複雑さの理論やアルゴリズムについてのセミナーです． 2006 年 1 月以来，とんと開いていません． すみませんです．．． でも，ときどき見てやってください．
• ランダム学グループ： 東工大内の数理科学の研究者の有志で作った研究体です． 上記ニュースにあります「計算世界観」グローバルＣＯＥに発展解消しました．

その他（宣伝？）

• Ｗｅｂ鼎談の総集編（０２年完成）． 「ＣＳから基礎科学が生まれるか？」について東方の三県人が熱く語っています． 是非，お立ちより下さい．
• 教養としてのコンピュータ・サイエンス入門（０１年９月）． 真のコンピュータ・サイエンスにふれてみて下さい．
• スキーが好きで，シーズン中は戸隠スキー場へよく行きます． その時期に，長野周辺，あるいはスキー場近辺の大学での非常勤講師が ありましたら，是非，お声をかけて下さい． 無給でも喜んでお引き受けいたします．

２．研究に関係したこと

研究テーマと関連の文献・リンク

• Computational Complexity Theory:
  • P versus NP problem (worst case):
    - J. Cai and O.Watanabe, On proving circuit lower bounds against the polynomial-time hierarchy, SIAM Journal on Computing, 33(4): 984--1009, 2004.
    - J. Cai and O.Watanabe, Random access to advice strings and collapsing result, Algorithmica, 45(1): 43--57, 2006.
  • P versus NP problem (average case):
    == Average-Case Complexity Forum (by Jie Wang).
  • Design and analysis of randomized algorithms:
    - M.Onsjoe and O.Watanabe, A simple message passing algorithm for graph partition problem, ISAAC'06, LNCS 4288:507-516, 2006.
    - O.Watanabe and M.Onsjoe, Finding most likely solutions, CiE'07, LNCS:, 2007.
• Applications of Theory of Computation:
  • Computational Learning and Discovery Science:
    - C. Domingo and O. Watanabe, MadaBoost: A modification of AdaBoost, COLT'00, Proc. 180--189, 2000.
    - C. Domingo, R. Gavalda, and O. Watanabe, Adaptive sampling methods for scaling up knowledge discovery algorithms, Data Mining and Knowledge Discovery, 6(2): 131--152, 2002.
    == Algorithmic Learning Theory (ALT) Workshop Archives.
    == Discovery Science home page.
  • Computational Analysis of Brain

書いた物の中から：解説＆私のたわごとです

すべて html 版，軽量です．

• 戸田誠之助氏ゲーデル賞授賞！： ＬＡ会誌の記事より，
• ネヴァリンナ賞（組合せ数学・離散数学のフィールズ賞）の取り方！？
• 離散数学のススメ
• ＮＰ問題とその難しさ
• 確率的検査可能証明とその応用； もっと詳細な記事→ 「ＰＣＰ：驚異の証明検証法」（数学セミナー０３年連載）と その補足説明のページ．

もう少しまじめな解説，講義ノート，研究資料集

• 論文リスト一覧（html 版．最近の文献にはオンラインアクセスできます）
• 計算量理論（入門編）講義ノート (pdf file, 2002, 2005 revised)
• 計算量理論（最近の話題）講義ノート (pdf file, 2002, 2005 revised)
• Knowledge Discovery における Random Sampling の利用法 (pdf file, 2001)
• Algorithmic Aspect of Boosting (pdf file, 2001)
• SAT の例題生成に関するホームページ
• 科研費で行なった研究の成果（現在，更新中）

学術関係の奉仕活動

• Editor of Theoretical Computer Science (TCS)
• Editor of Theory of Computing Systems (TOCS) (former name: Mathematical Systems Theory (MST))
• Vice Chair of EATCS Japan Chapter
• コンピュテーション研究会委員長（06 年 5 月〜 08 年 4 月）

付録・関連リンク

• 特定領域：新世代の計算限界のホームページ
• 特定領域：確率的情報処理のホームページ（05 年で終了）
• 数理・計算科学専攻リサーチレポート一覧（私の 98 年以降の論文はここにあります）
• 計算工学専攻テクニカルレポート一覧（私の 97 年以前の論文はここにあります）

授業

０７年度後期

• コンピュータサイエンス入門： 授業ホームページ

０６年度前期

• アルゴリズムとデータ構造： 授業ホームページ

その他

• スーパーコンピュータ・コンテスト（コンピュータ好き高校生の電脳甲子園） へどうぞ！
• 科学技術リテラシーの運動にもかかわっています．
• スキーが上手になるには（ＩＷスキースクールに入るべし）