• Search Research Projects
  • Search Researchers
  • How to Use
  1. Back to previous page

Watanabe Osamu  渡辺 治

ORCIDConnect your ORCID iD *help
… Alternative Names

WATANABE Osamu  渡辺 治

渡辺 治  ワタナベ オサム

Less
Researcher Number 80158617
Other IDs
External Links
Affiliation (Current) 2022: 東京工業大学, その他, 理事・副学長
Affiliation (based on the past Project Information) *help 2018 – 2021: 東京工業大学, その他, 理事・副学長
2016 – 2017: 東京工業大学, 情報理工学院, 教授
2015: 東京工業大学, 情報理工学研究科, 教授
2013 – 2015: 東京工業大学, 大学院情報理工学研究科, 教授
2012 – 2014: 東京工業大学, 情報理工学(系)研究科, 教授 … More
2012: 東京工業大学, 情報理工学研究科, 教授
2009 – 2012: 東京工業大学, 大学院・情報理工学研究科, 教授
2009: 東京工業大学, 情報理工学研究科, 教授
2007: 東京工業大学, 大学院・情報理工学研究科, 教授
2006 – 2007: 東京工業大学, 情報理工学研究科, 教授
2005 – 2006: Tokyo Institute of Technology, Graduate School of Information Science and Engineering, Professor, 大学院情報理工学研究科, 教授
1997 – 2005: 東京工業大学, 大学院・情報理工学研究科, 教授
2003: 東京工業大学, 情報理工学研究科, 教授
2001: Tokyo Institute of Technology, Dept. of Computer Science, Professor, 情報理工学研究科, 教授
1994 – 1995: 東京工業大学, 大学院・情報理工学研究科, 助教授
1990: 東京工業大学, 工学部, 助教授
1988: Department of Computer Science lecturer, 工学部, 講師
1986 – 1987: 東京工業大学, 工学部, 助手 Less
Review Section/Research Field
Principal Investigator
計算機科学 / Science and Engineering / Medium-sized Section 60:Information science, computer engineering, and related fields
Except Principal Investigator
Fundamental theory of informatics / Science and Engineering / Intelligent informatics / 情報工学 / Informatics / Intelligent informatics / Communication/Network engineering
Keywords
Principal Investigator
制約解探索問題 / 計算限界解明 / 充足可能性問題 / 確率アルゴリズム / ランダマイズド計算 / Belief Propagation / 方位選択性 / 自己組織化 / 脳の計算モデル / 視覚野 … More / ランダムウォーク / 研究連携促進 / 研究拠点形成 / 若手研究者の育成 / 成果の総括 / 成果の波及 / 計算複雑さの理論 / アルゴリズム理論 / 計算量上下界解析 / 成果の総括と公表 / 計算限界解明手法の開拓 / 多視点からの連携研究 / 国際研究者交流 / 各種啓発・研究成果波及 / 若手研究者育成 / 多視点からの統合的解析 / 計算限界研究センター / 計算理論若手研究者育成 / ELC 秋学校 / ELC Seminar / ELC Workshop / 計算困難さの解析 / 計算困難さの相転移 / 解空間の構造 / 解の数え上げ問題 / 制約式充足可能性問題 / 平均時間計算量 / SOS法 / 解空間の離散体積計算問題 / 回路設計問題 / 計算限界の確定 / 解空間の構造解析 / 情報理論的解析 / 平均時計算量解析 / 限定計算における計算限界 / 強指数時間仮説 / 確率分布解析 / 劣線形領域計算 / 充足解探索 / 解の一意化 / 平均時計算複雑さ / 伝搬系アルゴリズム / 統計力学的解析 / 計算論的解析 / 最尤解探索問題 / NP問題 / 解探索アルゴリズム / アルゴリズムのテスト / テストデータ生成 / 平均的計算量 / NP最適化問題 / NP型問題 / 生成アルゴリズム / 時間計算量 / NP Problem / Search Algoritum / Algorithm Test / Test Instance Generation / Average-Case Complexity / 疎行列パリティー検査符号 / アルゴリズムの平均的解析 / 疎行列パリティ検査符号 / Belief Propagation法 / 統計力学的手法 / Probabilistic Algorithms / Randomized Algorithm / Constraint Satisfaction Problem / Low-Density Parity Check / Average-Case Analysis of Algorism / アルゴリズムの平均的挙動の解析 / 局所探索アルゴリズム / 擬似平均 / ブースティング / 乱択計算 / 局所探索法 / マルコフ過程 / 近似解析 / サンプリング技法 / 片誤り性 / 確立アルゴリズム / アルゴリズムの状態確率の変化 / Average-Case Analysis of Algorithms / Satisfiability Problem / Local Search Algorithms / Pseudo Expectation / Boosting / 研究成果とりまとめ / 計算限界 / 成果のとりまとめ / 若手育成 / 啓発活動 / 最小記述量 / 最小記述量計算 / P≠NP予想 / 計算論的学習理論 / 一方向関数 / 最小記述量計算問題 / 機械学習 / P≠NP予想 / 平均時計算量 / 平均時計算複雑度 / 学習可能性 / 情報セキュリティ / 情報セキュリティ技術 / 最小回路サイズ問題 / 回路計算量 / 質問計算量 / SAT問題 / 量子計算の基礎 … More
Except Principal Investigator
アルゴリズム / 確率アルゴリズム / 計算量理論 / 計算量 / レプリカ法 / 理論計算機科学 / アルゴリズム理論 / 理論的性能保証 / 計算困難問題 / 情報の補填 / 数理モデル化 / 分散アルゴリズム / 充足可能性問題 / 経路積分法 / 反復解法 / tree width / 離散アルゴリズム / 離散最適化 / 品質保証 / 近似アルゴリズム / オンラインアルゴリズム / 量子アルゴリズム / 情報セキュリティー / 黯号 / 計数量 / 電子署名 / 暗号 / 暗号理論 / 相対化 / 暗号プロトコル / 安全性 / 匿名性 / 確率推論 / 確率伝搬法 / 要約伝搬法 / レプリカ対称性の破れ / スピングラス / レプリカ拡張 / レプリカ対称性 / 平均場近似 / 解析接続 / 複素零点評価 / レプリカ数 / ランダム行列理論 / TAP方程式 / 確立伝搬法 / 適応TPA法 / フィッシャー情報量 / ランダムネス / 自然計算 / 計算機科学 / 構成的アプローチ / 構成的生物学 / ハイブリッドシステム / 構成的材料工学 / 多体システム / 超分散 / ロバスト計算 / 性質検査 / グラフ問題 / アルゴリズム的ゲーム理論 / 乱化計算 / 劣線形時間 / 乱化アルゴリズム / 准線形時間 / キャビティ法 / グラフ分割問題 / スペクトラル法 / ランダム行列 / 評価表現辞書構築 / 自然言語処理 / ダイナミクス / 反復過程 / 空洞法 / 反復アルゴリズム / 並列処理 / 組合せ問題 / 離散構造 / 計算幾何学 / ネットワ-ク / 分散処理 / Algorithm / Parallel processing / Combinatorial problem / Discrete structure / Computational geometry / Network / Distributed processing / 学習 / サンプリング / ブースティング / 線形分離 / 部分系列探索 / テキスト分類 / 最小記述長基準に基づいた圧縮 / 半定形データ / 特徴空間の幾何学構造 / 学習可能性 / エキスパートオンラインモデル / 決定リスト / 適応型サンプリング / 質問学習 / 能動学習 / クラスタリング / 枝刈り / 方向選択性 / 強化学習 / learning / sampling / boosting / linear classifier / search for subsequence patterns / text categorization / MDL-based compression / semi-structured data / アルゴリズム工学 / グラフ理論 / 同型性判定問題 / 同型写像数え上げ問題 / Jones多項式 / グラフ文法 / 独立点集合問題 / 同型性判定 / 全域木 / マッチング / 二分決定グラフ / 辺連結度 / 完全独立全域木 / サイクル被覆 / 独立点集合 / 木幅 / 連結性判定問題 / 到達可能性判定問題 / グラフ認識問題 / グラフ同型性判定問題 / algorithm engineering / computational complexity / graph theory / isomorphism problem / isomorphism counting / Jones polynomial / graph grammar / 属性文法 / 仕様記述 / 関数型言語 / ソフトウェアプロセス / オブジェクトベース / ソフトウェア環境 / プログラミング環境 / プロセスモデル / 自動生成 / 記憶領域割当 / ソフトウェア仕様記述 / オブジェクト管理 / ソフトウェア自動生成 / オブジェクト指向 / 大域的領域割当て / Attribute Grammar / Software Development / Software Process / Hierarchical and Functional Programming / Object-Oriented Programming / 経路積分 / 疎結合系 / 符号理論 / 情報理論 / 統計力学 / LDPC符号 / 疎グラフ / ランダムグラフ / 情報統計力学 / 確率的手法 / グラフ / グループテスト / ランダム Less
  • Research Projects

    (23 results)
  • Research Products

    (134 results)
  • Co-Researchers

    (70 People)
  •  Computational Complexity of Minimum Description Size ProblemsPrincipal Investigator

    • Principal Investigator
      渡辺 治
    • Project Period (FY)
      2018 – 2021
    • Research Category
      Grant-in-Aid for Scientific Research (A)
    • Review Section
      Medium-sized Section 60:Information science, computer engineering, and related fields
    • Research Institution
      Tokyo Institute of Technology
  •  Exploring the Limits of ComputationPrincipal Investigator

    • Principal Investigator
      渡辺 治
    • Project Period (FY)
      2017
    • Research Category
      Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
    • Research Institution
      Tokyo Institute of Technology
  •  Analysis of Iterative Solvers for Structured MAX-XORSAT

    • Principal Investigator
      Mimura Kazushi
    • Project Period (FY)
      2013 – 2015
    • Research Category
      Grant-in-Aid for Scientific Research (C)
    • Research Field
      Intelligent informatics
    • Research Institution
      Hiroshima City University
  •  Expanding and Deepning Probabilistic Method in Coding Theory

    • Principal Investigator
      Wadayama Tadashi
    • Project Period (FY)
      2013 – 2015
    • Research Category
      Grant-in-Aid for Scientific Research (B)
    • Research Field
      Communication/Network engineering
    • Research Institution
      Nagoya Institute of Technology
  •  A multifaceted approach toward understanding the limitations of computationArea Organizer

    • Area Organizer
      渡辺 治
    • Project Period (FY)
      2012 – 2016
    • Research Category
      Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
  •  A Multifaced Approach Toward Understanding the Limitations of CompuationPrincipal Investigator

    • Principal Investigator
      Watanabe Osamu
    • Project Period (FY)
      2012 – 2016
    • Research Category
      Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
    • Review Section
      Science and Engineering
    • Research Institution
      Tokyo Institute of Technology
  •  Exploring the Limits of Computation from the Statistical PhysicsPrincipal Investigator

    • Principal Investigator
      Watanabe Osamu
    • Project Period (FY)
      2012 – 2016
    • Research Category
      Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
    • Review Section
      Science and Engineering
    • Research Institution
      Tokyo Institute of Technology
  •  Studies on Algorithms for Insufficient Spatial Information

    • Principal Investigator
      IWAMA Kazuo
    • Project Period (FY)
      2010 – 2012
    • Research Category
      Grant-in-Aid for Scientific Research (A)
    • Research Field
      Fundamental theory of informatics
    • Research Institution
      Kyoto University
  •  Graph bisection problem: approaches from statistical mechanics and theoretical computer science

    • Principal Investigator
      KABASHIMA Yoshiyuki
    • Project Period (FY)
      2010 – 2013
    • Research Category
      Grant-in-Aid for Scientific Research (B)
    • Research Field
      Fundamental theory of informatics
    • Research Institution
      Tokyo Institute of Technology
  •  Analysis of Iterative Algorithms for MAX-XORSAT problems

    • Principal Investigator
      MIMURA Kazushi
    • Project Period (FY)
      2010 – 2012
    • Research Category
      Grant-in-Aid for Scientific Research (C)
    • Research Field
      Intelligent informatics
    • Research Institution
      Hiroshima City University
  •  Design and Analysis of Algorithms for Insufficient Information

    • Principal Investigator
      IWAMA Kazuo
    • Project Period (FY)
      2007 – 2009
    • Research Category
      Grant-in-Aid for Scientific Research (A)
    • Research Field
      Fundamental theory of informatics
    • Research Institution
      Kyoto University
  •  Study on replica extension of approximate probability calculation algorithms

    • Principal Investigator
      KABASHIMA Yoshiyuki
    • Project Period (FY)
      2006 – 2009
    • Research Category
      Grant-in-Aid for Scientific Research on Priority Areas
    • Review Section
      Science and Engineering
    • Research Institution
      Tokyo Institute of Technology
  •  計算機科学における離散と連続に関する調査と新しい展開

    • Principal Investigator
      YAMASHITA Masafumi
    • Project Period (FY)
      2006
    • Research Category
      Grant-in-Aid for Scientific Research (C)
    • Research Field
      Fundamental theory of informatics
    • Research Institution
      Kyushu University
  •  暗号解折手法の計算量理論とよる改良とそれに基づく暗号方式

    • Principal Investigator
      田中 圭介
    • Project Period (FY)
      2004 – 2007
    • Research Category
      Grant-in-Aid for Scientific Research on Priority Areas
    • Review Section
      Science and Engineering
    • Research Institution
      Tokyo Institute of Technology
  •  離散アルゴリズムの品質保証技術に関する調査と新しい展開

    • Principal Investigator
      IWAMA Kazuo
    • Project Period (FY)
      2003
    • Research Category
      Grant-in-Aid for Scientific Research (C)
    • Research Field
      Fundamental theory of informatics
    • Research Institution
      Kyoto University
  •  AlgorithmicAnalysis of Statistical Mechanical HeuristicsPrincipal Investigator

    • Principal Investigator
      WATANABE Osamu
    • Project Period (FY)
      2002 – 2005
    • Research Category
      Grant-in-Aid for Scientific Research on Priority Areas
    • Review Section
      Science and Engineering
    • Research Institution
      Tokyo Institute of Technology
  •  Analyses of Randomized Algorithms for Constraint Satisfaction ProblemsPrincipal Investigator

    • Principal Investigator
      WATANABE Osamu
    • Project Period (FY)
      2001 – 2002
    • Research Category
      Grant-in-Aid for Scientific Research (C)
    • Research Field
      計算機科学
    • Research Institution
      Tokyo Institute of Technology
  •  Computational Methodology for Knowledge Discovery

    • Principal Investigator
      MARUOKA Akira
    • Project Period (FY)
      1998 – 2000
    • Research Category
      Grant-in-Aid for Scientific Research on Priority Areas (A)
    • Research Institution
      Tohoku University
  •  Analyzing Computational Complexity of Graph-Theoretic Problems with Restrictions on Width Parameters

    • Principal Investigator
      TODA Seinosuke
    • Project Period (FY)
      1998 – 2000
    • Research Category
      Grant-in-Aid for Scientific Research on Priority Areas (B)
    • Research Institution
      Nihon University
  •  個々のニューロンの動作原理に基づいた脳機能の解明Principal Investigator

    • Principal Investigator
      渡辺 治
    • Project Period (FY)
      1997 – 1998
    • Research Category
      Grant-in-Aid for Exploratory Research
    • Research Field
      計算機科学
    • Research Institution
      Tokyo Institute of Technology
  •  Test Instance Generation for NP-Search ProblemsPrincipal Investigator

    • Principal Investigator
      WATANABE Osamu
    • Project Period (FY)
      1994 – 1995
    • Research Category
      Grant-in-Aid for General Scientific Research (C)
    • Research Field
      計算機科学
    • Research Institution
      TOKYO INSTITUTE OF TECHNOLOGY
  •  Research on efficient algorithms for discrete structures

    • Principal Investigator
      NISHIZEKI Takao
    • Project Period (FY)
      1990 – 1991
    • Research Category
      Grant-in-Aid for Co-operative Research (A)
    • Research Field
      情報工学
    • Research Institution
      Tohoku University
  •  Study on the Construction of Software Development Environment based on the Attribute Grammar Formalisms

    • Principal Investigator
      KATAYAMA Takuya
    • Project Period (FY)
      1986 – 1988
    • Research Category
      Grant-in-Aid for General Scientific Research (A)
    • Research Field
      Informatics
    • Research Institution
      Tokyo Institute of Technology

All 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 Other

All Journal Article Presentation Book

  • [Book] コンピュータサイエンス2015

    • Author(s)
      渡辺治
    • Total Pages
      182
    • Publisher
      丸善サイエンスパレット
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Book] コンピュータサイエンス2015

    • Author(s)
      渡辺治
    • Total Pages
      182
    • Publisher
      丸善サイエンスパレット
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Book] 今度こそわかるP≠NP予想2014

    • Author(s)
      渡辺治
    • Publisher
      講談社
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Book] ELC International Meeting on Inference, Computation, and Spin Glasses (ICSG2013)2013

    • Author(s)
      Yoshiyuki Kabashima, Koji Hukushima, Jun-ichi Inoue, Toshiyuki Tanaka and Osamu Watanabe Eds
    • Publisher
      IOP Science, Journal of Physics: Conference Series
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Book] Randomness through Computation (H. Zenil ed.), Chapter 242011

    • Author(s)
      O.Watanabe(分担執筆)
    • Publisher
      World Scientific
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Book] Randomness through ComputationのChapter 24(H.Zenil ed.)2011

    • Author(s)
      O.Watanabe(分担執筆)
    • Publisher
      World Scientific
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Book] ブースティング(学習アルゴリズムの設計技法)2006

    • Author(s)
      渡辺治, 金森敬文, 畑埜晃平
    • Total Pages
      207
    • Publisher
      森北出版
    • Description
      「研究成果報告書概要(和文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Book] 森北出版2006

    • Author(s)
      金森敬文, 畑埜晃平, 渡辺治
    • Total Pages
      224
    • Publisher
      ブースティング-学習アルゴリズムの設計技法
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Book] ブースティング-学習アルゴリズムの設計技法2006

    • Author(s)
      金森敬文, 畑埜晃平, 渡辺治
    • Publisher
      森北出版
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Book] ブースティング-学習アルゴリズムの設計技法2006

    • Author(s)
      金森敬文, 畑埜晃平, 渡辺治
    • Total Pages
      224
    • Publisher
      森北出版
    • Data Source
      KAKENHI-PROJECT-16092206
  • [Journal Article] On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets2020

    • Author(s)
      Hirahara Shuichi、Watanabe Osamu
    • Journal Title

      Complexity and Approximation - In Memory of Ker-I Ko

      Volume: LNCS 12000 Pages: 67-79

    • DOI

      10.1007/978-3-030-41672-0_6

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18H04090
  • [Journal Article] An improvement of the algorithm of Hertli for the Unique 3SAT problem2019

    • Author(s)
      Tong Qin, Osamu Watanabe
    • Journal Title

      Theoretical Computer Science

      Volume: 印刷中

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18H04090
  • [Journal Article] Polynomial size linear programs for problems in P2019

    • Author(s)
      David Avis, David Bremner, Hans Tiwary and Osamu Watanabe
    • Journal Title

      Discrete Applied Mathematics

      Volume: online Pages: 22-39

    • DOI

      10.1016/j.dam.2019.03.016

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-16H02785, KAKENHI-PROJECT-18H04090
  • [Journal Article] A space-efficient separator algorithm for planar graphs2019

    • Author(s)
      Ryo Ashida, Sebastian Kuhnert, Osamu Watanabe
    • Journal Title

      IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Science

      Volume: 印刷中

    • NAID

      130007699441

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18H04090
  • [Journal Article] An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem2018

    • Author(s)
      Qin Tong、Watanabe Osamu
    • Journal Title

      Proc. of the 12th International Conference and Workshops on Algorithms and Computation

      Volume: LNCS Pages: 93-105

    • DOI

      10.1007/978-3-319-75172-6_9

    • Peer Reviewed
    • Data Source
      KAKENHI-WRAPUP-17H06074
  • [Journal Article] The Query Complexity of Witness Finding2017

    • Author(s)
      Kawachi Akinori、Rossman Benjamin、Watanabe Osamu
    • Journal Title

      Theory of Computing Systems

      Volume: 61 Pages: 305-321

    • DOI

      10.1007/s00224-016-9708-y

    • NAID

      120006582539

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-WRAPUP-17H06074
  • [Journal Article] Local Restrictions from the Furst-Saxe-Sipser Paper2017

    • Author(s)
      S. Tamaki and O. Watanabe
    • Journal Title

      Theory of Computing Systems

      Volume: 60(1) Pages: 20-32

    • DOI

      10.1007/s00224-016-9730-0

    • NAID

      120006582572

    • Peer Reviewed / Acknowledgement Compliant / Open Access
    • Data Source
      KAKENHI-PLANNED-24106008, KAKENHI-PROJECT-26330011, KAKENHI-WRAPUP-17H06074
  • [Journal Article] 解説:スーパーコンピューティングコンテスト 20162017

    • Author(s)
      渡辺治
    • Journal Title

      数学セミナー

      Volume: 1月号

    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Journal Article] Relating sublinear space computability among graph connectivity and related problems2016

    • Author(s)
      S. Hasegawa and T. Itoh
    • Journal Title

      in Proc. of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'16)

      Volume: LNCS 9627 Pages: 17-28

    • DOI

      10.1007/978-3-662-49192-8_2

    • Peer Reviewed / Acknowledgement Compliant
    • Data Source
      KAKENHI-PLANNED-24106008, KAKENHI-ORGANIZER-24106001
  • [Journal Article] A short implicant of a CNF formula with many satisfying assignments2016

    • Author(s)
      D. M. Kane and O. Watanabe
    • Journal Title

      Algorithmica

      Volume: online

    • DOI

      10.1007/s00453-016-0125-z

    • NAID

      120006582489

    • Peer Reviewed / Acknowledgement Compliant / Int'l Joint Research
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Journal Article] Resilience of antagonistic networks with regard to the effects of initial failures and degree-degree correlations2016

    • Author(s)
      S. Watanabe and Y. Kabashima
    • Journal Title

      Physical Review E

      Volume: 94

    • DOI

      10.1103/physreve.94.032308

    • Peer Reviewed / Acknowledgement Compliant / Open Access
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Journal Article] Limits of minimum circuit size problem as oracle2016

    • Author(s)
      S. Hirahara and O. Watanabe
    • Journal Title

      Proceedings of 31st Computational Complexity Conference (CCC)

      Volume: LIPIcs 18

    • DOI

      10.4230/LIPIcs.CCC.2016.18

    • Peer Reviewed / Acknowledgement Compliant / Open Access
    • Data Source
      KAKENHI-PLANNED-24106008, KAKENHI-PROJECT-16J06743
  • [Journal Article] Generalized shortest path kernel on graphs2015

    • Author(s)
      L. Hermansson, F. D. Johansson, and O. Watanabe
    • Journal Title

      Proc. of the 18th International Conference on Discovery Science (DS'15)

      Volume: LNCS 9356 Pages: 78-85

    • DOI

      10.1007/978-3-319-24282-8_8

    • Peer Reviewed / Acknowledgement Compliant / Int'l Joint Research
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Journal Article] Interval graph representation with given interval and intersection lengths2015

    • Author(s)
      J. Kobler, S. Kuhnert, and O. Watanabe
    • Journal Title

      J. Discrete Algorithms

      Volume: 34 Pages: 108-117

    • DOI

      10.1016/j.jda.2015.05.011

    • Peer Reviewed / Acknowledgement Compliant / Int'l Joint Research
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Journal Article] On the limit of some algorithmic approach to circuit lower bounds2014

    • Author(s)
      Osamu Watanabe
    • Journal Title

      Computing with New Resources

      Volume: LNCS8808 Pages: 394-405

    • DOI

      10.1007/978-3-319-13350-8_29

    • Acknowledgement Compliant
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Journal Article] A short implicant of a CNF formula with many satisfying assignments2014

    • Author(s)
      Daniel M. Kane, Osamu Watanabe
    • Journal Title

      Proc. 25th Sympos. on Algoerithms and Computation

      Volume: LNCS 8889 Pages: 273-284

    • DOI

      10.1007/978-3-319-13075-0_22

    • NAID

      120006582489

    • Peer Reviewed
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Journal Article] The Query Complexity of Witness Finding2014

    • Author(s)
      Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
    • Journal Title

      CSR 2014

      Volume: LNCS 8476 Pages: 218-231

    • DOI

      10.1007/978-3-319-06686-8_17

    • NAID

      120006582539

    • Peer Reviewed
    • Data Source
      KAKENHI-PLANNED-24106008, KAKENHI-PLANNED-24106009, KAKENHI-PROJECT-24240001, KAKENHI-PLANNED-24106002
  • [Journal Article] Cavity-based robustness analysis of interdependent networks: Influences of intranetwork and internetwork degree-degree correlations2014

    • Author(s)
      S.Watanabe and Y.Kabashima
    • Journal Title

      Physical Review E

      Volume: E 89

    • DOI

      10.1103/physreve.89.012808

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003, KAKENHI-PLANNED-25120013
  • [Journal Article] The query complexity of witness finding2014

    • Author(s)
      A. Kawachi, B. Rossmany and O. Watanabe
    • Journal Title

      Proc. of the 9th International Computer Science Symposium in Russia

      Volume: 未定

    • NAID

      120006582539

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Journal Article] スーパーコンピューティング・コンテスト (SuperCon13)2014

    • Author(s)
      渡辺治,遠藤敏雄
    • Journal Title

      数学セミナー

      Volume: 53(1) Pages: 50-55

    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Journal Article] Cavity approach to complex networks2014

    • Author(s)
      Y. Kabashima and S. Watanabe
    • Journal Title

      Topologica

      Volume: 未定

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Journal Article] O(sqrt(n))-space and polynomial-time algorithm for planar directed graph reachability2014

    • Author(s)
      Tetsuo Asano, David G. Kirkpatrick, Koutaro Nakagawa, Osamu Watanabe
    • Journal Title

      Proc. the 39th Symposium on Mathematical Foundations of Computer Science

      Volume: LNCS 8635 Pages: 45-56

    • DOI

      10.1007/978-3-662-44465-8_5

    • Peer Reviewed / Acknowledgement Compliant
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Journal Article] Derandomizing the HSSW algorithm for 3-SAT2013

    • Author(s)
      O.Watanabe
    • Journal Title

      Algorithmica

      Volume: 66 Pages: 112-124

    • DOI

      10.1007/s00453-013-9762-7

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003, KAKENHI-PLANNED-24106008
  • [Journal Article] A short implicant of CNFs with relatively many satisfying assignments2013

    • Author(s)
      Daniel Kane, Osamu Watanabe
    • Journal Title

      Electronic Colloquium on Computatinoal Complexity

      Volume: TR13-176

    • Data Source
      KAKENHI-PLANNED-24106008
  • [Journal Article] Is Valiant-Varirani's isolation probability improvable?2013

    • Author(s)
      Holger Dell, Valentine Kabanets,Dieter van Melkebeek, Osamu Watanabe
    • Journal Title

      Computational Complexity

      Volume: 22(2) Pages: 345-383

    • DOI

      10.1007/s00037-013-0059-7

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22240001, KAKENHI-PROJECT-22300003, KAKENHI-PLANNED-24106008
  • [Journal Article] An O(n^{{1/2}+epsilon}})-space and polynomial-time algorithm for directed planar reachability2013

    • Author(s)
      Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N.V. Vinodchandran, Osamu Watanabe
    • Journal Title

      Proc. of the 28th Conference on Computational Complexity

      Volume: 無し Pages: 277-286

    • DOI

      10.1109/ccc.2013.35

    • Peer Reviewed
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Journal Article] 特集:P ≠ NP 予想最前線2013

    • Author(s)
      渡辺治,西村治道,垂井淳,岡本吉央,瀧本英二,吉田悠一,上原隆平
    • Journal Title

      数学セミナー

      Volume: .52(12) Pages: 8-43

    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Journal Article] On the optimality of lattices for the Coppersmith technique2012

    • Author(s)
      Y. Aono, M. Agrawal, T. Satoh, and O. Watanabe
    • Journal Title

      Proc. 17th Australasian Conference on Information Security and Privacy (ACISP 2012) LNCS

      Volume: 7372 Pages: 376-389

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Journal Article] Propagation connectivity of random hypergraphs2012

    • Author(s)
      Amin Coja-Oghlan, Mikael Onsjo, and Osamu Watanabe (Osamu Watanabe)
    • Journal Title

      The Electronic Journal of Combinatorics

      Volume: 19(P17) Pages: 1-25

    • Peer Reviewed
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Journal Article] Propagation connectivity of random hypergraphs2012

    • Author(s)
      A.Coja-Oghlan, M.Onjo and O.Watanabe
    • Journal Title

      The Electronic Journal of Combinatorics

      Volume: 19 Pages: 1-25

    • URL

      http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p17

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Journal Article] Estimating the Gowers norm of modulo functions over prime fields2012

    • Author(s)
      A. Kawachi, H. Tanaka, and O. Watanabe
    • Journal Title

      IEICE Transactions on Information and Systems

      Volume: E95-D(3) Pages: 755-762

    • NAID

      10030611565

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Journal Article] Estimating the Gowers Norm of Modulo Functions over Prime Fields2012

    • Author(s)
      A.Kawachi, H.Tanaka, O.Watanabe
    • Journal Title

      IEICE Transactions on Information and Systems

      Volume: 95-D Issue: 3 Pages: 755-762

    • DOI

      10.1587/transinf.e95.d.755

      10.1587/transinf.E95.D.755

    • NAID

      10030611565

    • ISSN
      0916-8532, 1745-1361
    • Language
      English
    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-21300002, KAKENHI-PROJECT-22300003, KAKENHI-PLANNED-24106008
  • [Journal Article] Spectral Analysis of Random Sparse Matrices2011

    • Author(s)
      T.Ando, Y.Kabashima, H.Takahashi, O.Watanabe and M.Yamamoto
    • Journal Title

      IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

      Volume: E94-D(6) Issue: 6 Pages: 1247-1256

    • DOI

      10.1587/transfun.e94.a.1247

      10.1587/transfun.E94.A.1247

    • NAID

      10029802201

    • ISSN
      0916-8508, 1745-1337
    • Language
      English
    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Journal Article] Average-case analysis for the MAX-2SAT problem.2010

    • Author(s)
      Osamu Watanabe, Masaki Yamamoto
    • Journal Title

      Theor. Comput. Sci. 411(16-18)

      Pages: 1685-1697

    • NAID

      10018162837

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-19200001
  • [Journal Article] Average-case analysis for the MAX-2SAT problem2010

    • Author(s)
      O. Watanabe, M. Yamamoto
    • Journal Title

      Theoretical Computer Science 411

      Pages: 1685-1697

    • NAID

      10018162837

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] Weighted random popular matchings2010

    • Author(s)
      Toshiya Itoh, Osamu Watanabe
    • Journal Title

      Random Struct.Algorithms

      Volume: 37(4) Pages: 477-494

    • DOI

      10.1002/rsa.20316

    • NAID

      110006343680

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22240001
  • [Journal Article] Propagation connectivity of random hypergraphs2010

    • Author(s)
      A.Coja-Oghlan, M.Onsjo, O.Watanabe
    • Journal Title

      Lecture Notes on Computer Science

      Volume: 6302 Pages: 490-503

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Journal Article] Cavity approach to first eigenvalue problem in a family of symmetric random sparse matrices2010

    • Author(s)
      Y.Kabashima, H.Takahashi, O.Watanabe
    • Journal Title

      J.Phys.Conf.Ser.

      Volume: 233 Pages: 0120011-11

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Journal Article] On the complexity of kings2010

    • Author(s)
      E. Hemaspaandra, L. Hemaspaandra, T. Tantau, O. Watanabe
    • Journal Title

      Theoretical Computer Science 411

      Pages: 783-798

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] Finding most likely solutions2009

    • Author(s)
      M. Onsjoe, O. Watanabe
    • Journal Title

      Theoretical of Computing Systems 45

      Pages: 926-942

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] Finding Most Likely Solutions.2009

    • Author(s)
      Mikael Onsjo, Osamu Watanabe
    • Journal Title

      Theory Comput. Syst. 45(4)

      Pages: 926-942

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-19200001
  • [Journal Article] Scale free interval graphs2009

    • Author(s)
      N. Miyoshi, T. Shigezumi, R. Uehara, O. Watanabe
    • Journal Title

      Theoretical Computer Science 410

      Pages: 4588-4600

    • NAID

      120002511579

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] Randomized algorithms for 3-SAT2008

    • Author(s)
      O.〜Watanabe
    • Journal Title

      Theory of Computing Systerms (掲載 決定)

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-16092206
  • [Journal Article] Randomized algorithms for 3-SAT2007

    • Author(s)
      T. Hofmeister, U. Schoning, R. Schuler, O. Watanabe
    • Journal Title

      Theory of Computing Systems 40

      Pages: 249-262

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] Finding most likely solutkons2007

    • Author(s)
      O. Watanabe and M. Onsjoe
    • Journal Title

      LNCS(Proc. CiE 2007) 4497

      Pages: 758-767

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] Randomized Algorithms for 3-SAT2007

    • Author(s)
      T. Hofmeister, U. Schoening, R. Schuler, O. Watanabe
    • Journal Title

      Theory Comput. Syst. 40(3)

      Pages: 249-262

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-19200001
  • [Journal Article] Random access to advice strings and collapsing result2006

    • Author(s)
      J.Y.Cai, O.Watanabe
    • Journal Title

      Algorithmica 45

      Pages: 43-57

    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] A message passing algorithm for MAX2SAT2006

    • Author(s)
      渡辺治, 山本真基
    • Journal Title

      電子情報通信学会全国大会 D-S

      Pages: 19-20

    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Distributions in the Ehrenfest process2006

    • Author(s)
      S.Balaji, H.M.Mahmoud, O.Watanabe
    • Journal Title

      Statistics and Probability Letters 76

      Pages: 666-674

    • Data Source
      KAKENHI-PROJECT-16092206
  • [Journal Article] Random access to advice strings and collapsing result2006

    • Author(s)
      J.Y.Cay, O.Watanabe
    • Journal Title

      Algorithmica 45

      Pages: 43-57

    • Data Source
      KAKENHI-PROJECT-16092206
  • [Journal Article] Boosting--Design Method for Learning Algorithms (in Japanese)2006

    • Author(s)
      O.Watanabe, T.Kanamori, K.Hatano
    • Journal Title

      Morikita Pub. Co. Ltd.

      Pages: 207-207

    • Description
      「研究成果報告書概要(欧文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Average-case analysis for the MAX-2SAT problem2006

    • Author(s)
      O.Watanabe, M.Yamamoto
    • Journal Title

      Proc. Int'l Conf. on Theory and Applications of Satisfiability Testing LNCS 4142

      Pages: 277-282

    • NAID

      10018162837

    • Description
      「研究成果報告書概要(和文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Distributions in the Ehrenfest process2006

    • Author(s)
      S.Balaji, H.M.Mahmoud, 0.Watanabe
    • Journal Title

      Statistics and Prob. Letters Vol.76, No.7

      Pages: 666-674

    • Description
      「研究成果報告書概要(欧文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Distributions in the Ehrenfest process2006

    • Author(s)
      S.Balaji, H.M.Mahmoud, O.Watanabe
    • Journal Title

      Statistics and Probability Letters 76

      Pages: 666-674

    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] Distributions in the Ehrenfest process2006

    • Author(s)
      S. Balaji, H.M. Mahmoud, O. Watanabe
    • Journal Title

      Statistics and Probability Letters 76

      Pages: 666-674

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] Distributions in the Ehrenfest process2006

    • Author(s)
      S.Balaji, H.M.Mahmoud, O.Watanabe
    • Journal Title

      Statistics and Probability Letters Vol.76, No.7

      Pages: 666-674

    • Description
      「研究成果報告書概要(和文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Average-case analysis for the MAX-2SAT problem2006

    • Author(s)
      O.Watanabe, M.Yamamoto
    • Journal Title

      Proc. Int'l Conference on Theory and Applications of Satisfiability Testing LNCS 4142

      Pages: 277-282

    • NAID

      10018162837

    • Description
      「研究成果報告書概要(欧文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Random access to advice strings and collapsing result2006

    • Author(s)
      J. Cai, O. Watanabe
    • Journal Title

      Algorithmca 45

      Pages: 43-57

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Journal Article] Some heuristic analysis of local search algorithms for SAT problems2005

    • Author(s)
      O.Watanabe
    • Journal Title

      3rd International Symposium on Stochastic Algorithms LNCS 3777

      Pages: 14-24

    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Some heuristic analysis of local search algorithms for SAT problems2005

    • Author(s)
      O.Watanabe
    • Journal Title

      Proc. Int'l Symposium on Stochastic Algorithms LNCS 3777

      Pages: 14-24

    • Description
      「研究成果報告書概要(欧文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Sequential sampling techniques for algorithmic learning theory2005

    • Author(s)
      O.Watanabe
    • Journal Title

      Theoretical Computer Science Vol. 348

      Pages: 3-14

    • Description
      「研究成果報告書概要(欧文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Some heuristic analysis of local search algorithms for SAT problems2005

    • Author(s)
      O.Watanabe
    • Journal Title

      Proc. Int'l Sympos on Stochastic Algorithms LNCS 3777

      Pages: 14-24

    • Description
      「研究成果報告書概要(和文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Pseudo Expectation : A Tool for Analyzing Local Search Algorithm2005

    • Author(s)
      O.Watanabe
    • Journal Title

      Progress of Theoretical Physics Vol. 157

      Pages: 338-344

    • NAID

      110001276036

    • Description
      「研究成果報告書概要(和文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Sequential sampling techniques for algorithmic learning theory2005

    • Author(s)
      O.Watanabe
    • Journal Title

      Theoretical Computer Science 348

      Pages: 3-14

    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Learning of r-of-k functions by boosting2004

    • Author(s)
      K.Hatano, O.Watanabe
    • Journal Title

      Proc.15^<th> Intl Conference on Algorithmic Learning Theory LNCS3244

      Pages: 114-126

    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Relativized collapsing between BPP and PH under stringent oracle access2004

    • Author(s)
      J.Y.Cai, O.Watanabe
    • Journal Title

      Information Processing Letter 90

      Pages: 147-154

    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] On proving circuit lower bounds against the polynomial-time hierarch2004

    • Author(s)
      J.Y.Cai, O.Watanabe
    • Journal Title

      SIAM J.Computing 33・4

      Pages: 984-1009

    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Learning of r-of-k functions by boosting2004

    • Author(s)
      K.Hatano, O.Watanabe
    • Journal Title

      Proc. Int'l Conference on Algorithmic Learning Theory LNCS 3244

      Pages: 114-126

    • Description
      「研究成果報告書概要(和文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Analysis of a randomized local search algorithm for LDPCC decoding problem2003

    • Author(s)
      O.Watanabe, T.Sawai, H.Takayashi
    • Journal Title

      Proc. Int'l Symposium on Stochastic Algorithms LNCS 2827

      Pages: 50-60

    • Description
      「研究成果報告書概要(欧文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Analysis of a randomized local search algorithm for LDPCC decoding problem2003

    • Author(s)
      O.Watanabe, T.Sawai, H.Takayashi
    • Journal Title

      Proc. Int'l Sympos on Stochastic Algorithms LNCS 2827

      Pages: 50-60

    • Description
      「研究成果報告書概要(和文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Adaptive sampling methods for scaling up knowledge discovery algorithm2002

    • Author(s)
      C.Domingo, R.Gavalda, O.Watanabe
    • Journal Title

      Data Mining and Knowledge Discovery Vol.6, No.2

      Pages: 131-152

    • Description
      「研究成果報告書概要(和文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Adaptive sampling methods for scaling up knowledge discovery algorithms2002

    • Author(s)
      C.Domingo, R.Gavalda, 0.Watanabe
    • Journal Title

      Data Mining and Knowledge Discovery Vol. 6 No. 2

      Pages: 131-152

    • Description
      「研究成果報告書概要(欧文)」より
    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Randomized algorithms for 3-SAT

    • Author(s)
      Osamu Watanabe
    • Journal Title

      Theory of Computing Systems

    • Data Source
      KAKENHI-PROJECT-16092206
  • [Journal Article] On proving circuit lower bounds against the polynomial-time hierarchy

    • Author(s)
      J.Cai, O.Watanabe
    • Journal Title

      SIAM Journal on Computing 33(4)

      Pages: 984-1009

    • Data Source
      KAKENHI-PROJECT-16092206
  • [Journal Article] Pseudo Expectation : A Tool for Analyzing Local Search Algorithm

    • Author(s)
      O.Watanabe
    • Journal Title

      Progress of Theoretical Physics (掲載予定)

    • NAID

      110001276036

    • Data Source
      KAKENHI-PROJECT-14084207
  • [Journal Article] Relativized collapsing between BPP and PH under stringent oracle access

    • Author(s)
      J.Cai, O.Watanabe
    • Journal Title

      Information Processing Letters 90

      Pages: 147-154

    • Data Source
      KAKENHI-PROJECT-16092206
  • [Journal Article] Spectral Analysis of Random Sparse Matrices

    • Author(s)
      T.Ando, Y.Kabashima, H.Takahashi, O.Watanabe, M.Yamamoto
    • Journal Title

      IEICE TRANS. ED

      Volume: (to appear)

    • NAID

      10029802201

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Journal Article] Distributions in the Ehrenfest process

    • Author(s)
      S.Balaji, H.M.Mahmoud, O.Watanabe
    • Journal Title

      Statistics and Probability Letters 掲載予定

    • Data Source
      KAKENHI-PROJECT-14084207
  • [Presentation] Space Efficient Separator Algorithms for Planar Graphs2020

    • Author(s)
      Watanabe Osamu
    • Organizer
      Algorithms and Computation - 14th International Conference
    • Invited / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-18H04090
  • [Presentation] The robustness of LWPP and WPP, with an application to graph reconstruction2018

    • Author(s)
      Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
    • Organizer
      The 43rd International Symposium on Mathematical Foundations of Computer Science
    • Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-18H04090
  • [Presentation] 新学術領域「多面的アプローチの統合による計算限界の解明」成果報告2018

    • Author(s)
      渡辺 治
    • Organizer
      電子情報通信学会,コンピュテーション研究会
    • Invited
    • Data Source
      KAKENHI-WRAPUP-17H06074
  • [Presentation] Extension of the vertex cover problem to the size-t cycle cover problems2017

    • Author(s)
      B. Dashdemberel and O. Watanabe
    • Organizer
      電子情報通信学会,コンピュテーション研究会
    • Place of Presentation
      名古屋市
    • Year and Date
      2017-03-07
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Presentation] オラクルとしての回路最小化問題の限界2016

    • Author(s)
      平原秀一,渡辺治
    • Organizer
      2015 年度冬のLA シンポジウム
    • Place of Presentation
      京都大学
    • Year and Date
      2016-01-26
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Presentation] 新学術領域「計算限界解明」の紹介2016

    • Author(s)
      渡辺治
    • Organizer
      WINTER FESTA
    • Place of Presentation
      一橋講堂,東京
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] Relating sublinear space computability among graph connectivity and related problems2016

    • Author(s)
      T. Imai and O. Watanabe
    • Organizer
      The 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'16)
    • Place of Presentation
      Harrachov, Czech Rep.
    • Year and Date
      2016-01-23
    • Invited / Int'l Joint Research
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Presentation] 「多面的アプローチの統合による計算限界の解明」について2015

    • Author(s)
      渡辺治
    • Organizer
      JST ERATO 合同ワークショップ
    • Place of Presentation
      日本未来館
    • Year and Date
      2015-01-24
    • Invited
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] 新学術領域「計算限界解明」の紹介2015

    • Author(s)
      渡辺治
    • Organizer
      NII 情報系 Winter Festa
    • Place of Presentation
      国立情報学研究所
    • Year and Date
      2015-12-23
    • Invited
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] Sublinear space complexity2015

    • Author(s)
      O. Watanabe
    • Organizer
      Workshop on Connection between Algorithm Design and Complexity Theory
    • Place of Presentation
      Simons Institute
    • Year and Date
      2015-09-28
    • Invited / Int'l Joint Research
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Presentation] Sublinear space complexity2015

    • Author(s)
      Osamu Watanabe
    • Organizer
      Workshop on Connection between Algorithm Design and Complexity Theory
    • Place of Presentation
      Simons Institute (UC. Berkley)
    • Year and Date
      2015-09-28
    • Invited / Int'l Joint Research
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] 計算限界への挑戦:P=NPの世界を目指して2014

    • Author(s)
      渡辺治
    • Organizer
      OR学会第26回RAMPシンポジウム
    • Place of Presentation
      法政大学
    • Year and Date
      2014-10-17
    • Invited
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] The strong exponential time hypothesis and the structure of the solution space of CNF-SAT problems2014

    • Author(s)
      Osamu Watanabe
    • Organizer
      Workshop on Collective Dynamics in Information Systems at Kavli Institute for Theoretical Physics China
    • Place of Presentation
      Chinese Academy of Sciences, Beijin
    • Year and Date
      2014-10-10
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Presentation] Cavity-based robustness analysis of complex networks2013

    • Author(s)
      Y.Kabashima and S.Watanabe
    • Organizer
      East Asia Joint Seminars on Statistical Physics
    • Place of Presentation
      Kyoto, Japan
    • Year and Date
      2013-10-22
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Presentation] Cavity-based robustness analysis of intra- and inter-correlated network2013

    • Author(s)
      Shunsuke Watanabe and Yoshiyuki Kabashima
    • Organizer
      STATPHYS25, Seoul
    • Place of Presentation
      Seoul, Korea
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Presentation] Cavity approach to complex networks2013

    • Author(s)
      Y.Kabashima and S.Watanabe
    • Organizer
      International Workshop on Phase Transition, Critical Phenomena and Related Topics on Complex Networks
    • Place of Presentation
      Sapporo, Japan
    • Year and Date
      2013-09-09
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Presentation] Cavity approach to complex networks2013

    • Author(s)
      Y. Kabashima and S. Watanabe
    • Organizer
      International Workshop on Phase Transition, Critical Phenomena and Related Topics on Complex Networks
    • Place of Presentation
      北海道大学
    • Invited
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Presentation] Cavity-based robustness analysis of complex networks2013

    • Author(s)
      Yoshiyuki Kabashima and Shunsuke Watanabe
    • Organizer
      East Asia Joint Seminars on Statistical Physics
    • Place of Presentation
      京都大学
    • Invited
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Presentation] Message passing algorithms for MLS-3LIN problem2012

    • Author(s)
      O.Watanabe
    • Organizer
      The 9^<th> Meeting on Analytic Algorithms and Combinatorics (ANALCO'12)
    • Place of Presentation
      Kyoto Japan
    • Year and Date
      2012-01-16
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Presentation] On the optimality of lattices for the Coppersmith technique2012

    • Author(s)
      Yasunori Aono, Manindra Agrawal, Takakazu Satoh, and Osamu Watanabe
    • Organizer
      The 17th Australasian Conference on Information Security and Privacy
    • Place of Presentation
      Wollongong, Australia
    • Year and Date
      2012-07-09
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Presentation] Message passing algorithms for MLS-3LIN problem2012

    • Author(s)
      Osamu Watanabe
    • Organizer
      The 9th Meeting on Analytic Algorithmics and Combinatrics (ANALCO'12)
    • Place of Presentation
      Kyoto, Japan
    • Year and Date
      2012-01-16
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Presentation] 計算複雑さへの招待(1):基本+平均時計算複雑さ2012

    • Author(s)
      渡辺治
    • Organizer
      電子情報通信学会コンピュテーション研究会
    • Place of Presentation
      九州大学(福岡県)
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] Interval graphg representation with given interval and intersection lengths2012

    • Author(s)
      Johannes Koebler, Sebastian Kuhnert, and Osamu Watanabe (Osamu Watanabe)
    • Organizer
      The 23rd International Symposium on Algorithms and Computation
    • Place of Presentation
      Taipei, Taiwan
    • Year and Date
      2012-12-19
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Presentation] 新学術領域「計算限界解明」発足にあたって2012

    • Author(s)
      渡辺治
    • Organizer
      電子情報通信学会コンピュテーション研究会
    • Place of Presentation
      法政大学(東京都)
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] Evaluations of hash distributed A^* in optimal sequence alignment2011

    • Author(s)
      Y.Kobayashi, A.Kishimoto, O.Watanabe
    • Organizer
      The 22th International Joint Conference on Artificial Intelligence (IJCAI'11)
    • Place of Presentation
      Barcelona, Spain
    • Year and Date
      2011-07-22
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Presentation] Evaluations of Hash Distributed A* in Optimal Sequence Alignment2011

    • Author(s)
      Yoshikazu Kobayashi, Akihiro Kishimoto,Osamu Watanabe
    • Organizer
      IJCAI
    • Place of Presentation
      Barcelona,Spain
    • Year and Date
      2011-07-22
    • Data Source
      KAKENHI-PROJECT-22240001
  • [Presentation] Finding most-likely solution of the perturbed k-linear-equation problem2011

    • Author(s)
      Osamu Watanabe
    • Organizer
      Interdisciplinary Applications of Statistical Physics & Complex Networks
    • Place of Presentation
      Beijing, China
    • Year and Date
      2011-03-07
    • Data Source
      KAKENHI-PROJECT-22300003
  • [Presentation] 疎なランダム行列の第1固有値に関するcavity解析2010

    • Author(s)
      樺島祥介, 高橋久尚, 渡辺治
    • Organizer
      日本物理学会
    • Place of Presentation
      岡山大学
    • Year and Date
      2010-03-20
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] A new model for a scale-free hierarchical structure of isolated cliques2010

    • Author(s)
      T. Shigezumi, Y. Uno, O. Watanabe
    • Organizer
      4th Workshop on Algorithms and Computation
    • Place of Presentation
      Dhaka, Bangladesh
    • Year and Date
      2010-02-10
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] Cavity approach to the first eigenvalue problem in a family of symmetric random sparse matrices2010

    • Author(s)
      Y.Kabashima, H.Takahashi, O.Watanabe
    • Organizer
      International Workshop on Statistical-Mechanical Informatics
    • Place of Presentation
      Shiran-Kaikan, Kyoto, Japan
    • Year and Date
      2010-03-07
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] Cavity approach to the first eigenvalue problem in a family of symmetric random sparse matrices2010

    • Author(s)
      Y. Kabashima, H. Takahashi, O. Watanabe
    • Organizer
      Internationa Workshop on Statistical Mechanical Informatics 2010
    • Place of Presentation
      Kyoto, Japan
    • Year and Date
      2010-03-07
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] 正解が埋め込まれたグラフ等分割問題の統計力学的解析2009

    • Author(s)
      樺島祥介, 渡辺治, 山本真基
    • Organizer
      日本物理学会
    • Place of Presentation
      熊本大学
    • Year and Date
      2009-09-25
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] One-way functions and the Berman-Hartmanis conjecture2009

    • Author(s)
      M. Agrawal, O. Watanabe
    • Organizer
      24th Conference on Computational Complexity
    • Place of Presentation
      Paris, France
    • Year and Date
      2009-07-16
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] On spectral analysis of large low-density random matrices: rigorous vs. cavity analysis2009

    • Author(s)
      Y. Kabashima, O. Watanabe
    • Organizer
      Workshop on Techniques and Challenges from Statistical Physics
    • Place of Presentation
      Centre de Recerca Matem atica Bellaterra, Spain
    • Year and Date
      2009-10-14
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] On spectral analysis of large low-density random matrices : rigorous vs. cavity analysis2009

    • Author(s)
      Y.Kabashima, O.Watanabe
    • Organizer
      Workshop on Techniques and Challenges from Statistical Physics
    • Place of Presentation
      Centre de Recerca Matematica Bellaterra, Spain
    • Year and Date
      2009-10-14
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] Scale-free interval graphs2008

    • Author(s)
      N. Miyoshi, T. Shigezumi, R. Uehara, O. Watanabe
    • Organizer
      4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008)
    • Place of Presentation
      Shanghai, China
    • Year and Date
      2008-06-24
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] Complexity of finding most likely solutions2007

    • Author(s)
      O. Watanabe
    • Organizer
      コンプ研(電子情報通信学会)
    • Place of Presentation
      東北大学
    • Year and Date
      2007-10-16
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] 重みつき乱択最適選好マッチング2007

    • Author(s)
      伊東利哉, 渡辺治
    • Organizer
      コンプ研(電子情報通信学会)
    • Place of Presentation
      北海道大学
    • Year and Date
      2007-06-29
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] A simple message passing algorithm for graph partition problem2006

    • Author(s)
      M. Onsjoe, O. Watanabe
    • Organizer
      Algorithms and computation: 17th International Symposium, ISAAC 2006
    • Place of Presentation
      Kolkata, India
    • Year and Date
      2006-12-20
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] An improved upper bound for the three domatic number problems2006

    • Author(s)
      M.M. Halldorsson, O. Watanabe, M. Yamamoto
    • Organizer
      第5回情報科学技術フォーラム
    • Place of Presentation
      福岡大学
    • Year and Date
      2006-09-05
    • Data Source
      KAKENHI-PROJECT-18079006
  • [Presentation] 計算限界への挑戦:P=NPの世界を目指して

    • Author(s)
      渡辺治
    • Organizer
      E-サイエンスに向けた革新的アルゴリズム基盤第4回シンポジウム
    • Place of Presentation
      京都大学,日本
    • Invited
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] CNF formula with relatively many sat. assingments

    • Author(s)
      Osamu Watanabe
    • Organizer
      Banff Workshop on Computational Complexity
    • Place of Presentation
      BIRS Banff, Canada
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Presentation] 環境適応アルゴリズム

    • Author(s)
      渡辺治
    • Organizer
      CREST特定課題調査「ビッグデーター時代に向けた革新的アルゴリズム基盤」シンポジウム
    • Place of Presentation
      京都リサーチパーク,京都,日本
    • Invited
    • Data Source
      KAKENHI-PLANNED-24106008
  • [Presentation] 計算複雑さの理論とその進展

    • Author(s)
      渡辺治
    • Organizer
      東北大数学教室談話会
    • Place of Presentation
      東北大学,日本
    • Invited
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] 計算限界解明:なぜ限界を?&なぜ今?

    • Author(s)
      渡辺治
    • Organizer
      第12回情報科学技術フォーラム
    • Place of Presentation
      鳥取大学,日本
    • Invited
    • Data Source
      KAKENHI-ORGANIZER-24106001
  • [Presentation] Analysis of message passing algorithms for the 3XORSAT problem

    • Author(s)
      Takeshi Koshiba, Ryuhei Mori, Osamu Watanabe, Masaki Yamamoto
    • Organizer
      ELC Workshop on Inference, Computation, and Spin Glasses
    • Place of Presentation
      Sapporo, Japan
    • Data Source
      KAKENHI-PLANNED-24106008
  • 1.  TOKUYAMA Takeshi (40312631)
    # of Collaborated Projects: 5 results
    # of Collaborated Products: 0 results
  • 2.  IWAMA Kazuo (50131272)
    # of Collaborated Projects: 4 results
    # of Collaborated Products: 0 results
  • 3.  KABASHIMA Yoshiyuki (80260652)
    # of Collaborated Projects: 4 results
    # of Collaborated Products: 18 results
  • 4.  YAMASHITA Masafumi (00135419)
    # of Collaborated Projects: 4 results
    # of Collaborated Products: 0 results
  • 5.  KATOH Naoki (40145826)
    # of Collaborated Projects: 4 results
    # of Collaborated Products: 0 results
  • 6.  TODA Seinosuke (90172163)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 0 results
  • 7.  ASANO Takao (90124544)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 0 results
  • 8.  ITO Hiro (50283487)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 1 results
  • 9.  TAMAKI Suguru (40432413)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 1 results
  • 10.  HORIYAMA Takashi (60314530)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 0 results
  • 11.  MIMURA Kazushi (40353297)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 0 results
  • 12.  IMAI Hiroshi (80183010)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 1 results
  • 13.  MORI Ryuhei (60732857)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 1 results
  • 14.  AVIS David (90584110)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 1 results
  • 15.  HIRATA Tomio (10144205)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 16.  TAKEDA Koujin (70397040)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 17.  MIYAZAKI Shuichi (00303884)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 18.  SUGIHARA Kokichi (40144117)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 19.  MARUOKA Akira (50005427)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 20.  MAKINO Kazuhisa (60294162)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 21.  伊東 利哉 (20184674)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 1 results
  • 22.  KAWAHARA Jun (20572473)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 23.  MORIZUMI Hiroki (50463782)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 24.  IBARAKI Toshihide (50026192)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 25.  MINATO Shinichi (10374612)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 26.  KAWARABAYASHI Kazuhisa (40361159)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 27.  ASANO Tetsuo (90113133)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 28.  YAMASHITA Shigeru (30362833)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 29.  TAKIMOTO Eiji (50236395)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 1 results
  • 30.  HUKUSHIMA Koji (80282606)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 1 results
  • 31.  NISHIZEKI Takao (80005545)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 32.  WATANABE Toshimasa (80112184)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 33.  HAGIHARA Ken-ichi (00133140)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 34.  SHINOHARA Ayumi (00226151)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 35.  TAKASU Atsuhiro (90216648)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 36.  TANI Sei'ichi (70266708)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 37.  SAITO Akira (90186924)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 38.  YAKU Takeo (90102821)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 39.  CHEN Zhi-zhong (00242933)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 40.  KATAYAMA Takuya (70016468)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 41.  SAEKI Motoshi (80162254)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 42.  YONEZAKI Naoki (00126286)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 43.  Wadayama Tadashi (20275374)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 44.  IZUMI Taisuke (20432461)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 45.  IWATA Kenichi (80284313)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 46.  HAYASHI Kazunori (50346102)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 47.  櫻井 幸一 (60264066)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 48.  田中 圭介 (20334518)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 1 results
  • 49.  河内 亮周 (00397035)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 2 results
  • 50.  萩谷 昌巳 (30156252)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 51.  上田 和紀 (10257206)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 52.  山村 雅幸 (00220442)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 53.  増澤 利光 (50199692)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 54.  安藤 映 (20583511)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 55.  小柴 健史 (60400800)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 1 results
  • 56.  山本 真基 (50432414)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 2 results
  • 57.  安浦 寛人 (80135540)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 58.  梅尾 博司 (80132356)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 59.  五十嵐 善英 (60006260)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 60.  黒田 耕嗣 (50153416)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 61.  上原 隆平 (00256471)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 62.  天野 一幸 (30282031)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 63.  平原 秀一 (80848440)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 64.  清水 伸高 (10910127)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 65.  ABE Naoki
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 66.  Krzakala Florent
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 67.  Zdeborova Lenka
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 68.  Zhou Haijun
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 69.  Coolen A. C. C.
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 70.  WATANABE Sumio
    # of Collaborated Projects: 0 results
    # of Collaborated Products: 1 results

URL: 

Are you sure that you want to connect your ORCID iD to this researcher?
* This action can be performed only by the researcher themselves.

Information User Guide FAQ News Terms of Use Attribution of KAKENHI

Powered by NII kakenhi