Watanabe Osamu 渡辺治

… Alternative Names

Researcher Number	80158617
Other IDs
External Links
Affiliation (Current)	2021: 東京工業大学, その他, 理事・副学長
Affiliation (based on the past Project Information) *help	2018 – 2020: 東京工業大学, その他, 理事・副学長 2016 – 2017: 東京工業大学, 情報理工学院, 教授 2015: 東京工業大学, 情報理工学研究科, 教授 2013 – 2015: 東京工業大学, 大学院情報理工学研究科, 教授 2012 – 2014: 東京工業大学, 情報理工学(系)研究科, 教授 … More
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 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

Computational Complexity of Minimum Description Size ProblemsPrincipal InvestigatorOngoing
- 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

[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] 今度こそわかるＰ≠ＮＰ予想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
- Language
  English
- 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-Vazirani'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
  210000127990
- 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
  210000127990
- 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
  ＪＳＴ　ＥＲＡＴＯ　合同ワークショップ
- 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] 計算限界への挑戦：Ｐ＝ＮＰの世界を目指して2014
- Author(s)
  渡辺治
- Organizer
  ＯＲ学会第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] 計算限界への挑戦：Ｐ＝ＮＰの世界を目指して
- 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. ABE Naoki

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
65. Krzakala Florent

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
66. Zdeborova Lenka

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
67. Zhou Haijun

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
68. Coolen A. C. C.

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
69. WATANABE Sumio

# of Collaborated Projects: 0 results

# of Collaborated Products: 1 results

Watanabe Osamu 渡辺 治

WATANABE Osamu 渡辺 治

渡辺 治 ワタナベ オサム

Research Projects

Research Products

Co-Researchers

Computational Complexity of Minimum Description Size ProblemsPrincipal InvestigatorOngoing

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Exploring the Limits of ComputationPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

A multifaceted approach toward understanding the limitations of computationArea Organizer

Area Organizer

Project Period (FY)

Research Category

A Multifaced Approach Toward Understanding the Limitations of CompuationPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Exploring the Limits of Computation from the Statistical PhysicsPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Principal Investigator

Project Period (FY)

Watanabe Osamu 渡辺治

WATANABE Osamu 渡辺治

渡辺治ワタナベオサム