"Ryo Ashida,Sebastian Kuhnert,Osamu Watanabe","A Space-Efficient Separator Algorithm for Planar Graphs",,"IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences","The Institute of Electronics, Information and Communication Engineers","Vol. E102-A","No. 9","pp. 1007-1016",2019,Sept.
"Tong Qin,Osamu Watanabe","An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem","COMP","信学技報",,"vol. 117","no. 269","pp. 5-12",2017,Oct.
"Suguru Tamaki,Osamu Watanabe","Local Restrictions from the Furst-Saxe-Sipser Paper",,"Theory of Computing Systems",,"Vol. 60","No. 1","Page 20-32",2017,Jan.
"Akinori Kawachi,Benjamin Rossman,Osamu Watanabe","The Query Complexity of Witness Finding",,"Theory of Computing Systems",,"Vol. 61","No. 2","pp. 305?321",2016,Sept.
"Osamu Watanabe","Sublinear space complexity","Workshop on Connection between Algorithm Design and Complexity Theory",,,,,,2016,Sept.
"渡辺 治","この本！ おすすめします コンピューターサイエンスを教養に",,"情報管理","国立研究開発法人 科学技術振興機構","Vol. 59","No. 1",,2016,May
"Shuichi Hirahara,Osamu Watanabe","Limits of minimum circuit size problem as oracle","The 31st Conference on Computational Complexity","Proc. of the  31st Conference on Computational Complexity",,"Vol. LIPIcs 18",,"page 1-18",2016,May
"Daniel Kane,Osamu Watanabe","A short implicant of a CNF formula with many satisfying assignments",,"Algorithmica","Springer US","  76","  4","pp. 1203-1223",2016,Feb.
"Tatsuya Imai,Osamu Watanabe","Relating sublinear space computability","The 42nd Int'l Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'16)","SOFSEM 2016: Theory and Practice of Computer Science","Springer Berlin Heidelberg","Vol. LNCS 9587",,"pp. 17-28",2016,Jan.
"Linus Hermannson,Fredrik Johansson,Osamu Watanabe","Generalized shortest path kernel on graphs","Proc. of the 18th International Conference on Discovery Science (DS 2015)","Discovery Science","Springer International Publishing","Vol. LNCS 9356",,"pp. 78-85",2015,Oct.
"Johannes K?bler,Sebastian Kuhnert,Osamu Watanabe","Interval graph representation with given interval and intersection lengths",,"Journal of Discrete Algorithms","Elsevier","Vol. 34",,"pp. 108-117",2015,Sept.
"渡辺 治","コンピュータサイエンス ?計算を通して世界を観るー",,,"丸善サイエンスパレット",,,,2015,Sept.
"渡辺 治","新学術領域「計算限界解明」の研究紹介","NII 情報系 Winter Festa",,,,,,2015,
"O. Watanabe","On the limit of some algorithmic approach to circuit lower bounds","Computing with New Resources (Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday)","LNCS",,"Vol. 8808",,"pp. 394-405",2014,Dec.
"渡辺 治","計算限界への挑戦：Ｐ＝ＮＰの世界を目指して","第26回RAMPシンポジウム，ＯＲ学会",,,,,,2014,Oct.
"D. Kane,O. Watanabe","Implicant size of a CNF formula with many satisfying assignments","コンプ研，電子情報通信学会","信学技報 COMP2014-31",,,,,2014,Oct.
"O. Watanabe","The Strong Exponential Time Hypothesis and the structure of the solution space of CNF-SAT problems","Collective Dynamics in Information Systems, KITPC/ITP-CAS，中国科学院，北京",,,,,,2014,Oct.
"ケイン ダニエル,渡辺 治","多くの充足解を持つ和積形論理式のインプリカントの大きさについて",,"電子情報通信学会技術研究報告. COMP, コンピュテーション","一般社団法人電子情報通信学会","Vol. 114","No. 238",,2014,Sept.
"渡辺 治","スーパーコン : 高校生・高専生の電脳甲子園(<特集>若い力:高校生の問題解決)",,"オペレーションズ・リサーチ : 経営の科学","公益社団法人日本オペレーションズ・リサーチ学会","Vol. 59","No. 6",,2014,May
"O. Watanabe","Max k-linear equation problem","力学系と計算，京都大学",,,,,,2014,Jan.
"渡辺 治","環境適用型アルゴリズム","CREST特定課題調査「ビッグデーター時代に向けた革新的アルゴリズム基盤」シンポジウム，京都リサーチパーク",,,,,,2014,Jan.
"渡辺 治","「多面的アプローチの統合による計算限界の解明」について","JST ERATO 合同 WS，日本未来館",,,,,,2014,Jan.
"Tetsuo Asano,David Kirkpatrick,Kotaro Nakagawa,Osamu Watanabe","O(sqrt(n))-space and polynomial-time algorithm for planar directed graph reachability","Proc. of the 39th Sympos. on Mathematical Foundations of Computer Science (MFCS'14)","Lecture Notes in Computer Science","Springer Berlin Heidelberg","Vol. 8635",,"pp. 45-56",2014,
"渡辺 治","今度こそわかるＰ≠ＮＰ予想",,,"講談社サイエンティフィク",,,,2014,
"渡辺 治,遠藤 敏夫","スーパーコンピューティングコンテスト・2013",,"数学セミナー","日本評論社","Vol. 53","No. 1","pp. 50-55",2014,
"Akinori Kawachi,Benjamin Rossman,Osamu Watanabe","The query complexity of witness finding","Proc. of the 9th International Computer Science Symposium in Russia (CSR14)","Lecture Notes in Computer Science","Springer Berlin Heidelberg","Vol. 8476",,"pp. 218-231",2014,
"Daniel M. Kane,Osamu Watanabe","A short implicant of a CNF formula with many satisfying assignments","Proc. of the 25th Sympos. on Algoerithms and Computation (ISAAC'14)","Lecture Notes in Computer Science","Springer International Publishing","Vol. 8889",,"pp. 273-284",2014,
"渡辺 治","計算複雑さの理論とその進展","東北大学数学教室談話会",,,,,,2013,Dec.
"渡辺 治","計算限界解明：なぜ限界を？＆なぜ今？","FIT13，鳥取大学",,,,,,2013,Sept.
"Osamu Watanabe","Message passing algorithms for MLS-3LIN problem",,"Algorithmica",,"Vol. 66","No. 4","pp. 848-868",2013,Aug.
"渡辺 治","計算限界への挑戦：Ｐ＝ＮＰの世界を目指して","e-サイエンスシンポジウム，京都大学",,,,,,2013,June
"Holger Dell,Valentine Kabanets,Dieter van Melkebeek,Osamu Watanabe","Is Valiant-Vazirani's isolation probability improvable?",,"computational complexity",,"Vol. 22","No. 2","pp. 345-383",2013,June
"Tatsuya Imai,Kotaro Nakagawa,Aduri Pavan,Variyam Vinochandran,Osamu Watanabe","An O(sqrt(n)+eps})-Space Algorithm for Directed Planar Reachability with Polynomial Running Time","アルゴリズム研，情報処理学会","情処研報 AL",,,,,2013,May
"河内 亮周,ロスマン ベンジャミン,渡辺 治","NP-解探索における質問計算量について(一般)",,"電子情報通信学会技術研究報告. COMP, コンピュテーション","一般社団法人電子情報通信学会","Vol. 113","No. 50",,2013,Apr.
"河内 亮周,ロスマン ベンジャミン,渡辺 治","NP-解探索における質問計算量について",,"研究報告アルゴリズム（AL）","一般社団法人情報処理学会","Vol. 2013","No. 7",,2013,Apr.
"O. Watanabe","Introduction of the ELC project","ELC Tokyo Complexity Workshop",,,,,,2013,Mar.
"遊佐 俊彦,渡辺 治","DS-1-5 正規化圧縮距離の妥当性解析(DS-1.COMP学生シンポジウム,シンポジウムセッション)",,"電子情報通信学会総合大会講演論文集","一般社団法人電子情報通信学会","Vol. 2013","No. 1",,2013,Feb.
"渡辺 治","P≠NP予想って？",,"数学セミナー","日本評論社","Vol. 52","No. 12","pp. 8-12",2013,
"Tatsuya Imai,Kotaro Nakagawa,A. Pavan,N.V. Vinodchandran,Osamu Watanabe","An O(n^{{1/2}+epsilon}})-space and polynomial-time algorithm for directed planar reachability","Proc. of the 28th Conference on Computational Complexity (CCC'13)","Computational Complexity (CCC), 2013 IEEE Conference on","IEEE",,,"pp. 277-286",2013,
"渡辺 治","P≠NP予想最前線",,"数学セミナー","日本評論社","Vol. 52","No. 12","pp. 8-43",2013,
"山口 裕生,渡辺 治","べき則グラフ上での対立する噂の拡散の解析 : 二種類の次数の頂点からなるグラフの場合(一般)",,"電子情報通信学会技術研究報告. COMP, コンピュテーション","一般社団法人電子情報通信学会","Vol. 112","No. 340",,2012,Nov.
"渡辺 治","計算複雑さへの招待(1):基本+平均時計算複雑さ(特別企画)",,"電子情報通信学会技術研究報告. COMP, コンピュテーション","一般社団法人電子情報通信学会","Vol. 112","No. 340",,2012,Nov.
"O. Watanabe","Perturbed k-linear-equation problems",,"Workshop at IIT Kanpur",,,,,2012,Aug.
"渡辺 治","[招待講演]新学術領域「計算限界解明」発足にあたって",,"電子情報通信学会技術研究報告. COMP, コンピュテーション","一般社団法人電子情報通信学会","Vol. 112","No. 199",,2012,July
"渡辺 治","計算複雑さの研究って?",,"コンピュータソフトウェア","Japan Society for Software Science and Technology","Vol. 29","No. 2",,2012,Mar.
"A. Kawachi,H. Tanaka,O. Watanabe","Estimating the Gowers norm of modulo functions over prime fields",,"IEICE TRANSACTIONS on Information and Systems",,"Vol. E95-D","No. 3","pp. 755-762",2012,Mar.
"OSAMU WATANABE","Message passing algorithms for MLS-3LIN problem","9th Meeting on Analytic Algorithmics and Combinatrics","Proc. of the 9th Meeting on Analytic Algorithmics and Combinatrics","SIAM",,,"pp. 68--85",2012,Jan.
"Johannes K?bler,Sebastian Kuhnert,Osamu Watanabe","Interval graphg representation with given interval and intersection lengths","Proc. of the 23rd International Symposium on Algorithms and Computation (ISAAC'12)","Lecture Notes in Computer Science","Springer Berlin Heidelberg","Vol. 7676",,"pp. 517-526",2012,
"Amin Coja-Oghlan,Mikael Onsj?,Osamu Watanabe","Propagation connectivity of random hypergraphs",,"The Electronic Journal of Combinatorics",,"Vol. 19",,"pp. 1-25",2012,
"Yoshinori Aono,Manindra Agrawal,Takakazu Satoh,Osamu Watanabe","On the optimality of lattices for the Coppersmith technique","17th Australasian Conference on Information Security and Privacy (ACISP)","Lecture Notes in Computer Science","Springer Berlin Heidelberg","Vol. 7372",,"pp. 376-389",2012,
"Holger Dell,Valentine Kabanets,Dieter van Melkebeek,Osamu Watanabe","Is Valiant-Vazirani's isolation probability improvable?","Proc. of the 27th Conference on Computational Complexity (CCC'12)","Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on","IEEE",,,"pp. 1-20",2012,
"渡辺 治","計算複雑さの理論 : 我々は何を研究しているのか?",,"電子情報通信学会技術研究報告. COMP, コンピュテーション","一般社団法人電子情報通信学会","Vol. 111","No. 256",,2011,Sept.
"Takeya Shigezumi,Yushi Uno,Osamu Watanabe","A new model for a scale-free hierarchical structure of isolated clique",,"Journal of Graph Algorithms and Applications",,"Vol. 15","No. 5","pp. 661-682",2011,Aug.
"Y. Kobayashi,A. Kishimoto,O. Watanabe","Evaluations of hash distributed A* in optimal sequence alignment","29th International Joint Conference on Artificial Intelligence","IJCAI Proceedings",,,,"pp. 584--590",2011,June
"T. Ando,Y. Kabashima,H. Takahashi,O. Watanabe,M. Yamamoto","Spectral analysis of random sparse matrices",,"IEICE Transactions on Information and Systems","電子情報通信学会","Vol. E94-D","No. 6","pp. 1247--1256",2011,June
"OSAMU WATANABE","Randomness in Algorithms",,"Randomness through Computation","World Scientific",,,"pp. 297--308",2011,Feb.
"T. Asano,Nakano,Y. Okamoto,O. Watanabe","Algorithm and Computation, Proc. 22nd International Symposium on Algorithms and Computation (ISAAC'11)",,"Lecture Notes in Computer Science 7074","Springer-Verlag",,,,2011,
"O. Watanabe","Randomness in Algorithms (Chap.24 of Randomness through Computation (H. Zenil ed.))",,,"World Scientific","Vol. 24",,"pp. 297-308",2011,
"Toshiya Itoh,Osamu Watanabe","Weighted Random Popular Matchings",,"Random Structures and Algorithms","Wiley","Vol. 37","No. 4","pp. 477-494",2010,Dec.
"石畑 清,大岩 元,角田 博保,清水 謙多郎,玉井 哲雄,長崎 等,中里 秀則,中谷 多哉子,疋田 輝雄,三浦 孝夫,箕原 辰夫,和田 耕一,渡辺 治","理工系情報学科の授業内容分布のシラバスによる調査（中間報告）","情報教育シンポジウム","情報教育シンポジウム","情報処理学会 コンピュータと教育研究会",,,,2010,Aug.
"Amin Coja-Oghlan,Mikael Onsjo,Osamu Watanabe","Propagation connectivity of random hypergraph","Proc. 14th Intl. Workshop on Randomization and Computation (RANDOM'10)","in Proc. 14th Intl. Workshop on Randomization and Computation (RANDOM'10)","Springer","Vol. 6302",,,2010,Aug.
"Yoshiyuki Kabashima,Hisanao Takahashi,Osamu Watanabe","Cavity approach to the first eigenvalue problem in a family of symmetric random sparse matrices","International Workshop on Statistical-Mechanical Informatics 2010","Journal of Physics Conference Series","IOP","Vol. 233","No. 1","pp. 012001(1-11)",2010,July
"Y. Soejima,A. Kishimoto,O. Watanabe","Evaluating root parallelization in Go",,"IEEE Transactions on Computational Intelligence and AI in Games","IEEE","Vol. 2","No. 4","pp. 278--287",2010,Apr.
"Yoshinori Aono,Manindra Agrawal,Osamu Watanabe","On Coppersmith's technique and its limit","電子情報通信学会2010年総合大会, シンポジウム DS-1 ＣＯＭＰ学生シンポジウム",,,,,,2010,Mar.
"OSAMU WATANABE,Masaki Yamamoto","Average-case analysis for the MAX-2SAT problem",,"Theoretical Computer Science","Springer","Vol. 411","No. 16-18","pp. 1685--1697",2010,Mar.
"Takeya Shigezumi,Yushi Uno,OSAMU WATANABE","A new model for a scale-free hierarchical structure of isolated cliques","4th Workshop on Algorithms and Computation (WALCOM'10)","Proc. of 4th Workshop on Algorithms and Computation (WALCOM'10)","Springer","  LNCS 5942",,"pp. 216--227",2010,Feb.
"Edith Hemaspaandra,Lane Hemaspaandra,Till Tantau,OSAMU WATANABE","On the complexity of kings",,"Theoretical Computer Science","Elsevier","Vol. 411","No. 4-5","pp. 783-798",2010,Jan.
"渡辺 治","理論研究の役割（学会５０周年企画，情報処理技術の未来地図）",,"情報処理学会誌",,"Vol. 51","No. 5",,2010,
"渡辺 治","情報科学技術は人類の言葉",,"情報科学教育学会全国大会",,,,,2010,
"O. Watanabe,T. Zeugmann","Proc. 5th International Symposium on Stochastic Algorithms: Foundations and Applications (SAGA'10)",,"Lecture Notes in Computer Science 5792","Springer-Verlag",,,,2010,
"Mikael Onsj?,OSAMU WATANABE","Finding most likely solutions",,"Theory of Computing Systems","Springer","Vol. 45","No. 4","pp. 926-942",2009,Nov.
"副島佑介,岸本 章宏,渡辺治","モンテカルロ木探索のRoot並列化とコンピュータ囲碁での有効性について","第14回ゲーム・プログラミングワークショップ",,,,,,2009,Nov.
"副島佑介,岸本章宏,渡辺治","モンテカルロ木探索のroot並列化とコンピュータ囲碁での有効性について","第14回ゲーム・プログラミングワークショップ",,,,,"pp. 27--33",2009,Nov.
"Naoto Miyoshi,Takeya Shigezumi,Ryuhei Uehara,Osamu Watanabe","Scale free interval graphs",,"Theoretical Computer Science",,"vol. 410","no. 45","pp. 4588-4600",2009,Oct.
"Yoshiyuki Kabashima,Osamu Watanabe","On spectral analysis of large low-density random matrices: rigorous vs. cavity analysis","Workshop on Techniques and Challenges from Statistical Physics",,,,,,2009,Oct.
"OSAMU WATANABE,Thomas Zeugmann","Proceedings of 5th International Symposium on Stochastic Algorithms: Foundations and Applications (SAGA'10)",,"Proceedings of 5th International Symposium on Stochastic Algorithms: Foundations and Applications (SAGA'10)",,"  LNCS 5792",,,2009,Oct.
"飯田勝吉,新里卓史,伊東利哉,渡辺治","キャンパス共通認証認可システムの構築と運用",,"電子情報通信学会",,"Vol. J92-B","No. 10","pp. 1554-1565",2009,Oct.
"Madhusuden Agrawal,OSAMU WATANABE","One-way functions and the Berman-Hartmanis conjecture","24th Conference on Computational Complexity",,,,,,2009,July
"Mikael Onsj?,OSAMU WATANABE","Implementation of a bit-parallel approximate string matching algorithm","情報処理学会アルゴリズム研究会",,"Information Processing Society of Japan","Vol. AL-124","No. 3",,2009,Mar.
"渡辺治,松田裕幸","スパコンをぶん回せ - スーパーコンピューティングコンテスト・2008",,"数学セミナー",,"Vol. 47","No. 12","pp. 41-45",2008,Dec.
"渡辺治,北野晃朗,木村泰紀,谷口雅治","数学の言葉と論理",,,"朝倉書店",,,,2008,Sept.
"Naoto Miyoshi,Takeya Shigezumi,Ryuhei Uehara,Osamu Watanabe","Scale-free interval graphs","4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008)","Algorithmic Aspects in Information and Management","Springer","vol. LNCS5034",,"pp. 292-303",2008,June
"Michael Sipser,太田和夫,阿部正幸,植田広樹,田中圭介,藤岡淳,渡辺治","計算理論の基礎 [原著第2版] 1. オートマトンと言語",,,"共立出版",,,,2008,May
"Michael Sipser,太田和夫,阿部正幸,植田広樹,田中圭介,藤岡淳,渡辺治","計算理論の基礎 [原著第2版] 3. 複雑さの理論",,,"共立出版",,,,2008,May
"Michael Sipser,太田和夫,阿部正幸,植田広樹,田中圭介,藤岡淳,渡辺治","計算理論の基礎 [原著第2版] 2. 計算可能性の理論",,,"共立出版",,,,2008,May
"Jose Balcazar,Yang Dai,Junichi Tanaka,OSAMU WATANABE","Provably fast training algorithms for support vector machines",,"Theory Computing Systems","Springer","Vol. 42","No. 4","pp. 568--595",2008,Apr.
"Takeya Shigezumi,Naoto Miyoshi,Ryuhei Uehara,Osamu Watanabe","Scale free interval graphs","The First Asian Association for Algorithms and Computation Annual Meeting (AAAC08)",,,,,,2008,Apr.
"Takeya Shigezumi,Naoto Miyoshi,Ryuhei Uehara,Osamu Watanabe","Scale free interval graphs","電子情報通信学会2008年総合大会",,,,,,2008,Mar.
"新里卓史,飯田勝吉,植松友彦,渡辺治","東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構","電子情報通信学会2008年総合大会","電子情報通信学会",,"  BS‐8‐3",,,2008,Mar.
"新里卓史,飯田勝吉,植松友彦,渡辺治","東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構の設計と実装",,"電子情報通信学会",,"Vol. 107","No. 449","pp. 45-50",2008,Jan.
"Naoto Miyoshi,Takeya Shigezumi,Ryuhei Uehara,Osamu Watanabe","Scale Free Interval Graphs","東京工業大学グローバル COE 「計算世界観の深化と展開」発足シンポジウム",,,,,,2007,Dec.
"Osamu Watanabe","Complexity of finding most likely solutions","コンプ研,電子情報通信学会","信学技報 COMP",,,,,2007,Oct.
"伊東利哉,渡辺治","重みつき乱択最適選好マッチング","コンプ研,電子情報通信学会","信学技報 COMP",,,,,2007,Oct.
"Takeya Shigezumi,上原隆平,Osamu Watanabe","Do interval graphs dream of scale-free network?","2007年夏のLAシンポジウム",,,,,,2007,July
"Osamu Watanabe,Mikael Onsjoe","Finding most likely solutions","Proc. Computation and Logic in the Real World (CiE 2007)","Lecture Notes in Computer Science","Springer","Vol. 4497",,"pp. 758-767",2007,June
"Thomas Hofmeister,Uwe Schoning,Rainer Schuler,Osamu Watanabe","Randomized algorithms for 3-SAT",,"Theoretical Computer Science",,"Vol. 40",,"pp. 249-262",2007,Jan.
"E. Hemaspaandra,L. Hemaspaandra,T. Tantau,O. Watanabe","On the complexity of kings","Fundamentals of Computation Theory : 16th International Symposium, FCT 2007","Lecture notes in computer science","Springer","Vol. 4639",,"pp. 328-340",2007,
"渡辺 治","でたらめさを利用した計算",,"科学","岩波書店","Vol. 10",,,2007,
"J. Cai,O. Watanabe","Stringent relativization: a new approach for studying complexity classes",,"SIGACT news",,"Vol. 37","No. #140",,2006,Dec.
"JinYi Cai,Osamu Watanabe","Random access to advice strings and collapsing result",,"Algorithmica",,"Vol. 45","No. 1","pp. 43-57",2006,Jan.
"金森 敬文,畑埜 晃平,渡辺 治","ブースティング --- 学習アルゴリズムの設計技法",,,"森北出版",,,,2006,
"S. Balaji,H.M. Mahmoud,O. Watanabe","Distributions in the Ehrenfest process",,"Statistics and Probability Letters",,"Vol. 76","No. 7","pp. 666-674",2006,
"O. Watanabe,M. Yamamoto","Average-case analysis for the MAX-2SAT problem","Theory and applications of satisfiability testing - SAT 2006 : 9th international conference","Lecture notes in computer science","Springer","Vol. 4121",,"pp. 277-282",2006,
"M. Onsjoe,O. Watanabe","A simple message passing algorithm for graph partition problem","Algorithms and computation : 17th International Symposium, ISAAC 2006,","Lecture Notes in Computer Science","Springer","Vol. 4288",,"pp. 507-516",2006,
"渡辺 治","教養としてのコンピュータ・サイエンス教育――東京工業大学での試み",,"情報処理",,"Vol. 47","No. 12","pp. 1372-1377",2006,
"M.M. Halldorsson,O. Watanabe,M. Yamamoto","An improved upper bound for the three domatic number problems","第7回情報科学技術フォーラム",,,,,,2006,
"渡辺 治,山本 真基","MAX-2SAT 問題の平均時間計算量の解析","コンプ研，電子情報通信学会","信学技報 COMP",,,,,2006,
"M. Onsjoe,渡辺 治","メッセージ伝播法によるグラフの分割アルゴリズム","アルゴリズム研，情報処理学会","情処研報 AL",,,,,2006,
"渡辺 治","ランダムネスの面白さ",,"数理科学","サイエンス社",,"No. 9",,2006,
"Osamu Watanabe","Some heuristic analysis of local search algorithms for SAT problems","The 3rd Int'l Sympos. on Stochastic Algorithms: Foundations and Applications","Lecture Notes in Computer Sciecne, Springer",,"Vol. 3777",,"pp. 14-25",2005,Oct.
"松田裕幸,渡辺治","スーパーコン甲子園",,,"日本評論社",,,,2005,June
"Osamu Watanabe","Pseudo expectation: A tool for analyzing local search algorithms",,"Progress of Theoretical Physics, Supplement",,,"No. 157","pp. 338-344",2005,Apr.
"M. Onsjoe,O. Watanabe","A message passing algorithm for the bisection problem","日韓ワークショップ",,,,,,2005,
"渡辺治","Computational Complexity and Its Applications","Theory and Applications of Models of Computation (TAMC05)",,,,,,2005,
"R. Kato,O. Watanabe","Substring search and repeat search using factor oracles",,"Information Processing Letters",,"Vol. 93","No. 6","pp. 269-274",2005,
"Osamu Watanabe","Sequential sampling techniques for algorithmic learning theory",,"Theoretical Computer Science",,"Vol. 348","No. 1-2","pp. 3-14",2005,
"Jin-Yi Cai,Osamu Watanabe","Relativized collapsing between BPP and PH under stringent oracle access",,"Information Processing Letters",,"Vol. 90",,"pp. 147-154",2004,
"Kouhei Hatano,Osamu Watanabe","Learning r-of-k functions by boosting",,"Proc. 15th International Conference on Algorithmic Learning Theory (ALT 2004)",,"Vol. LNCS3244",,"pp. 114-126",2004,
"O. Watanabe","Pseudo expectation: A tool for analyzing local search algorithms","Stat. Physics of Disordered Systems and its Applications","湘南国際村",,,,,2004,
"K. Hatano,O. Watanabe","Learning r-of-k functions by boosting","コンプ研，電子情報通信学会","信学技報 COMP",,,"No. 22","pp. 27-32",2004,
"O. Watanabe","Pseudo expectation: A tool for analyzing local search algorithms","Optimization algorithms and quantum disordered systems",,,,,,2004,
"Jin-Yi Cai,Osamu Watanabe","On proving circuit lower bounds against the polynomial-time hierarchy",,"SIAM Journal on Computing",,"Vol. 33","No. 4","pp. 984-1009",2004,
"Jin-Yi Cai,Osamu Watanabe","Random access to advice strings and collapsing results",,"Proc. 15th International Symposium on Algorithms and Computation (ISAAC'04)",,"Vol. LNCS3341",,"pp. 209-220",2004,
"新倉 康明,J. Schneider,渡辺 治","単純な規則で表されるマルコフ過程の近似解析手法","アルゴリズム研，情報処理学会","情処研報 AL",,,"No. 94","pp. 73-80",2004,
"J.Y. Cai,O. Watanabe","On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results",,"Proc. 9th International Computing and Combinatorics Conference",,"Vol. LNCS2697",,"pp. 202-211",2003,
"O. Watanabe,K. Sawai,H. Takahashi","Analysis of a randomized local search algorithm for LDPCC decoding problem",,"Proc. 2nd International Symposium on Stochastic Algorithms",,"Vol. LNCS2827",,"pp. 50-60",2003,
"S. Aida,M. Crasmaru,K. Regan,O. Watanabe","Games with a uniqueness property",,"Theory of Comput. Systems",,"Vol. 37",,"pp. 29-47",2003,
"O. Watanabe","Analysis of randomized algorithms for some constraint satisfaction problem","The NICHIDAI Symposium in hornor of the 100th anniversary celebration of College of Humanities and Sciences",,,,,,2003,
"O. Watanabe","P vs. NP and P vs. PSPACE","科研費基盤（Ｃ）企画研究，研究集会",,,,,,2003,
"O. Watanabe","Analysis of a randomized local search algorithm for LDPCC decoding problems","Joint Workshop of Hayashibara Foundation and SMAPIP",,,,,,2003,
"O. Watanabe","Analysis of a randomized local search algorithm for LDPCC decoding problems","Dagstuhl Seminar 03141",,,,,,2003,
"J. Cai,O. Watanabe","Stringent relativization",,"FST TCS 2003 : foundations of software technology and theoretical computer science : 23rd conference, Mumbai, India, December 15-17, 2003 : proceedings","Springer","Vol. LNCS 2914",,"pp. 408-419",2003,
"渡辺 治","ネヴァンリンナ賞業績紹介：スダン",,"数学セミナー","日本評論社","Vol. 42",,"pp. 44-49",2003,
"渡辺 治","ＰＣＰ：驚異の証明検証法",,"数学セミナー","日本評論社","Vol. 42","No. 7-10",,2003,
"渡辺 治","スーパーコンピュータ・コンテスト２００３",,"数学セミナー","日本評論社","Vol. 42","No. 12",,2003,
"J.Y. Cai,O. Watanabe","Relativized collapsing results under stringent oracle access","第１回情報科学技術フォーラム","情報技術レターズ","電子情報通信学会","Vol. 1","No. 1","pp. 1-2",2002,Sept.
"T. Hoffmaister,U. Schoening,R. Schuler,O. Watanabe","A Probabilistic 3-SAT Algorithm Further Improved",,"Proc. 19th Symposium on Theoretical Aspects of Computer Science (STACS'02)","Proc. 19th Symposium on Theoretical Aspects of Computer Science (STACS'02)","Vol. LNCS 2285",,"pp. 193-202",2002,
"S. Aida,M. Crasmaru,K. Regan,O.Watanabe","Games with a uniqueness property ",,"Proc. 19th Symposium on Theoretical Aspects of Computer Science ","Proc. 19th Symposium on Theoretical Aspects of Computer Science ","Vol. LNCS 2285",,"pp. 396-407",2002,
"渡辺 治","LDPCの複合化のためのランダム局所探索アルゴリズムの解析","北陸先端大学院大学 情報科学研究科セミナー",,,,,,2002,
"S. Aida,R. Schuler,T. Tsukiji,O. Watanabe","The difference between polynominal-time many-one and truth-table reducibilities on distributional problems",,"Theory of Comput. Systems",,"Vol. 35",,"pp. 449-463",2002,
"渡辺 治","ブースティング技法のアルゴリズム的考察",,"日本神経回路学会誌",,"Vol. 9","No. 3","pp. 196-203",2002,
"J. Balcazar,戴 陽,O. Watanabe","Provably fast trainning algorithms for support vector machines","コンプ研，電子情報通信学会","信学技報 COMP",,,"No. 66","pp. 25-32",2002,
"A. Sharma,O Watanabe","Algorithmic Learning Theory",,,"Elsevier",,,,2002,
"O. Watanabe","Algorithmic aspects of boosting",,"Progress in Discovery Science : final report of the Japanese dicsovery science project","Springer","Vol. LNAI 2281",,"pp. 349-359",2002,
"渡辺 治","ある制約式充足問題群の解法について","OR学会関西支部 OR若手研究者の会、離散アルゴリズム研究部会",,,,,,2002,
"渡辺治","教養としてのコンピュータ・サイエンス",,"サイエンス社","サイエンス社",,,,2001,
"K. Okamoto,O. Watanabe","Deterministic application of Grover's quantum search algorithm",,"Proc. 7th Annual Int'l Conf. on Computing and Combinatorics",,,,"pp. 493-501",2001,
"Jose Balcazar,Dai Yang,OSAMU WATANABE","A random sampling technique for training support vector machines: for primal-form maximal-margin classifiers",,"Proc. 12th Int'l Conference on Algorithmic Learning Theory, Lecture Notes in AI, Springer",,"Vol. 2225",,"pp. 119-134",2001,
"S. Aida,R. Schuler,T. Tsukiji,O. Watanabe","On the difference between polynomial-time many-one and truth-table reduciblities on distributional problems",,"Proc. 18th Int'l Sympos. on Theoretical Aspects of Computer Science",,,,"pp. 52-62",2001,
"OSAMU WATANABE","How can computer science contribute to knowlede discovery?",,"Proc. SOFSEM 2001, Lecture Notes in Computer Scinece, Springer",,"Vol. 2234",,"pp. 136-151",2001,
"R. Gavalda,O. Watanabe","Sequential sampling algorithms: Unified analysis and lower bounds","Stochastic Algorithms : Foundations and Applications : International Symposium, SAGA 2001","Lecture notes in computer science","Springer","Vol. 2264",,"pp. 173-187",2001,
"K. Amano,J. Tromp,O. Watanabe","On a generalized ruin problem","Approximation, randomization, and combinatorial optimization : algorithms and techniques : 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001","Lecture notes in computer science","Springer","Vol. 2129",,"pp. 181-191",2001,
"A. Sharma,O Watanabe","Special Issue on Algorithmic Learning Theory",,,"Elsevier",,,,2001,
"J. Balcazar,Y.Dai,O. Watanabe","Provably fast training algorithms for support vector machines","First IEEE International Conference on Data Mining (ICDM'01)","Proceedings, 2001 IEEE International Conference on Data Mining, 29 November-2 December 2001, San Jose, California","IEEE",,,"pp. 43-50",2001,
"太田和夫,渡辺治","計算理論の基礎",,,"共立出版",,,,2000,Apr.
"Carlos Domingo,Osamu Watanabe","MadaBoost: A modification of AdaBoost","3th Annual Confernce on Computational Learning Theory (COLT'00)","Proc. of 3th Annual Confernce on Computational Learning Theory (COLT'00)",,,,"pp. 180-189",2000,
"K. Amano,P. Vitanyi,O. Watanabe","On the length of the monopolist game","コンプ研，電子情報通信学会","信学技報 COMP",,,"No. 62","pp. 41-48",2000,
"渡辺 治","コンピュータサイエンスのための単純かつ効率的なサンプリング技法",,"発見科学とデータマイニング","共立出版",,,"pp. 86-96",2000,
"渡辺 治","計算を究める−アルゴリズムと計算の複雑さの研究",,"IT革命最前線：情報処理学会創立４０周年記念出版","情報処理学会",,,"pp. 201-209",2000,
"C. Domingo,O. Watanabe","Scaling up a boosting-based learner via adaptive sampling","Knowledge discovery and data mining : current issues and new applications : 4th Pacific-Asia Conference, PAKDD 2000","Lecture notes in artificial intelligence","Springer","Vol. 1805",,"pp. 317-328",2000,
"W. Lindner,R. Schuler,O. Watanabe","Resource-bounded measure and learnability",,"Theory of Comput. Systems",,"Vol. 33",,"pp. 151-170",2000,
"O. Watanabe","Sequential sampling techniques for algorithmic learning theory",,"Proc. 11th International Conference on Algorithmic Learning Theory (ALT'00)",,"Vol. 1968",,"pp. 27-40",2000,
"Kyoichi Okamoto,Osamu Watanabe","Deterministic application of Grover's quantum search algorithm","アルゴリズム研，情報処理学会","情処研報 AL",,,,,2000,
"OSAMU WATANABE","Simple sampling techniques for discovery science",,"IEICE Trans. Information and Systems",,"Vol. E83-D","No. 1","pp. 19-26",2000,
"O. Watanabe,T. Yokomori","Proc. 10th International Conference on Algorithmic Learning Theory",,,"Springer-Verlag",,,,1999,
"P.B. Miltersen,N.V. Vinodchandran,O. Watanabe","Super-polynomial verseus half-exponential circuit size exponential hierarchy","Computing and combinatorics : 5th Annual International Conference, COCOON '99,","Lecture notes in computer science","Springer","Vol. 1627",,"pp. 210-220",1999,
"Carlos Domingo,Ricard Gavald?,Osamu Watanabe","Adaptive sampling methods for scaling up knowledge discovery algorithms","2nd International Confernce on Discovery Science (DS'99)","Second International Conference, DS’99 Tokyo, Japan, December 6?8, 1999 Proceedings","Springer Berlin Heidelberg","Vol. 1721",,"pp. 172-183",1999,
"根上 生也,松井 知己,渡辺 治","Web 鼎談",,"数学セミナー","日本評論社","Vol. 99-00","No. 4-3",,1999,
"O. Watanabe","From learning theory to discovery science","Automata, languages and programming : 26th International Colloquium, ICALP '99","Lecture notes in computer science","Springer","Vol. 1644",,"pp. 134-148",1999,
"C. Domingo,O. Watanabe,T. Yamazaki","A role of constaint in self-organization","Randomization and approximation techniques in computer science : Second International Workshop, RANDOM '98","Lecture notes in computer science","Springer","Vol. 1518",,"pp. 307-318",1998,
"望月 厚,元木 光雄,渡辺 治","３充足可能性判定問題３ＳＡTの正例題生成手法の解析",,"情報処理学会論文誌",,"Vol. 39","No. 6","pp. 1850-1857",1998,
"C. Domingo,R. Gavalda,O. Watanabe","Practical algorithms for on-line sampling","Discovery science : first International Conference, DS '98","Lecture notes in artificial intelligence","Springer","Vol. 1532",,"pp. 150-162",1998,
"W. Lindner,R. Schuler,O. Watanabe","Resource bounded measure and learnability","Thirteenth Annual IEEE Conference on Computational Complexity (formerly: Structure in Complexity Theory Conference)","Proceedings, Thirteenth Annual IEEE Conference on Computational Complexity (formerly: Structure in Complexity Theory Conference), June 15-18, 1998, Buffalo, New York, USA","IEEE",,,"pp. 261-270",1998,
"J. Kobler,O.Watanabe","New collapse consequence of NP having small circuits",,"SIAM Journal on Computing",,"Vol. 28","No. 1","pp. 311-324",1998,
"L. Hemaspaandra,Z. Jiang,J. Rothe,O. Watanabe","Boolean operations, joins and the extended low hierarchy",,"Theoretical Computer Science",,"Vol. 205","No. 1-2","pp. 317-327",1998,
"C. Domingo,T. Tsukiji,O. Watanabe","Partial Occam's razor and its appliations","Algorithmic learning theory : 8th international workshop, ALT '97","Lecture notes in artificial intelligence","Springer","Vol. 1316",,"pp. 85-99",1997,
"S. Horie,O. Watanabe","Hard instance generataion for SAT","Algorithms and computation : 8th International Symposium, ISAAC '97","Lecture notes in computer science","Springer","Vol. 1350",,"pp. 22-31",1997,
"T. Motoki,渡辺 治","Test instance generators for SAT",,,,,,,1997,
"渡辺 治","東工大スーパーコンピュータコンテスト",,"数学セミナー","日本評論社","Vol. 36",,"pp. 67-71",1997,
"L. Hemaspaandra,Z. Jiang,J. Rothe,O. Watanabe","Pollynomial-time multi-selectivity",,"Journal of Universal Computer Science",,"Vol. 3","No. 3","pp. 197-229",1997,
"C. Domingo,T. Tsukiji,O. Watanabe","Partial Occam's razor its applications",,"Information Processing Letters",,"Vol. 64",,"pp. 179-185",1997,
"Ronald Book,Osamu Watanabe","On random hard sets for NP",,"Information and Computation",,"Vol. 125",,"pp. 70-76",1996,
"J. Balcazar,J. Diaz,R. Gavalda,O. Watanabe","An optimal parallel algorithm for learning DFA",,"Journal of Universal Computer Science",,"Vol. 2","No. 3","pp. 97-122",1996,
"L. Hemachandra,Z. Jiang,J. Rothe,O. Watanabe","The join can lower complexity","Computing and combinatorics : Second Annual International Conference, COCOON '96","Lecture notes in computer science","Springer","Vol. 1090",,"pp. 260-267",1996,
"Hoong Chuin Lau,Osamu Watanabe","Randomized approximation of the constraint satisfaction problem","5th Scandinavian Workshop on Algorithm Theory","5th Scandinavian Workshop on Algorithm Theory Reykjav?k, Iceland, July 3?5, 1996 Proceedings","Springer Berlin Heidelberg","Vol. 1097",,"pp. 76-87",1996,
"O. Watanabe,O. Yamashita","An improvement of the digital cash  protocol of Okamoto and Ohta","Algorithms and computation : 7th International Symposium, ISAAC '96","Lecture notes in computer science","Springer","Vol. 1178",,"pp. 436-445",1996,
"M. Ogiwara,T. Thierauf,S. Toda,O. Watanabe","On closure properties of #P in the context of PFo#P",,"Journal of Computer and System Sciences","Academic Press","Vol. 53","No. 2","pp. 171--179",1996,
"OSAMU WATANABE","Randomized approximation of the constraint satisfaction problem",,"Nordic Journal of Computing",,"Vol. 3",,"pp. 405-424",1996,
"T. Thierauf,S. Toda,O. Watanabe","On sets bounded truth-table reducible to P-selective sets",,"Theoretical Informatics and Applications",,"Vol. 30","No. 2","pp. 135-154",1996,
"太田和夫,黒澤馨,渡辺治","情報セキュリtィの科学",,"講談社ブルーバックス","講談社ブルーバックス",,,,1995,
"R. Schuler,O. Watanabe","Towards average-case complexity analysis of NP optimization problems","Tenth Annual Structure in Complexity Theory Conference","Proceedings of the tenth Annual Structure in Complexity Theory Conference, June 19-22, 1995, Minneapolis, Minnesota","IEEE",,,"pp. 148-159",1995,
"Luc Longpre,Osamu Watanabe","On Symmetry of Information and Polynomial Time Invertibility",,"Information and Computation",,"Vol. 121","No. 1","pp. 14-22",1995,
"渡辺 治","東工大スーパーコンピュータコンテスト",,"数学セミナー","日本評論社","Vol. 34",,"pp. 34-41",1995,
"太田 和夫,黒澤 肇,渡辺 治","情報セキュリティーの科学： マジック・プロトコルへの招待",,,"講談社ブルーバックス",,,,1995,
"J. Kobler,O. Watanabe","New collapse consequence of NP having small circuits","Automata, languages and programming : 22nd International Colloquium, ICALP 95","Lecture notes in computer science","Springer","Vol. 944",,"pp. 196-207",1995,
"J. Balcazar,J. Diaz,R. Gavalda,O. Watanabe","An optimal parallel algorithm for learning DFA","Seventh Annual ACM Conference on Computational Learning Theory : COLT 94","Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory : COLT 94 : July 12th-15th, 1994, New Brunswick, New Jersey","ACM",,,"pp. 208-217",1994,
"T. Tierauf,S. Toda,O. Watanabe","On sets bounded truth-table reducible to P-selective sets","STACS 94 : 11th Annual Symposium on Theoretical Aspects of Computer Science","Lecture notes in computer science","Springer-Verlag","Vol. 775",,"pp. 427-438",1994,
"R. Rao,J. Rothe,O. Watanabe","Upward separation for FewP and related classes",,"Information Processing Letters","Elsevier Science Publishers","Vol. 52","No. 4","pp. 175--180",1994,
"T. Thierauf,S. Toda,O. Watanabe","On closure properties of GapP",,"Computational Complexity","Birkhauser","Vol. 4",,"pp. 242--261",1994,
"R. Book,O. Watanabe","On random hard sets for NP","5th International Symposium on Algorithms and Computation (ISAAC'94)","5th International Symposium, ISAAC '94 Beijing, P. R. China, August 25?27, 1994 Proceedings",,"Vol. 834",,"pp. 47-55",1994,
"J. Balcazar,J. Diaz,R. Gavalda,O. Watanabe","The query complexity of learning DFA",,"New Generation Computing","Ohmsha","Vol. 12",,"pp. 337--358",1994,
"P. Orponen,K. Ko,U. Schoning,O. Watanabe","Instance Commplexity",,"Journal of the Association for Computing Machinery",,"Vol. 41","No. 1","pp. 96-121",1994,
"R. Gavalda,O. Watanabe","Structural analysis of polynomial time query learnability",,"Mathematical Systems Theory","Springer Verlag","Vol. 27",,"pp. 231--256",1994,
"O. Watanabe","A framework for polynomial time query learnability",,"Mathematical Systems Theory","Springer Verlag","Vol. 27",,"pp. 211--229",1994,
"Pekka Orponen,Uwe Schoening,Ker-I Ko,Osamu Watanabe","Instance Complexity(共著)",,"Journal of the Association for Computing Machiner,y",,"Vol. 41","No. 1","pp. 96-121",1994,
"渡辺 治","一方向関数の基礎理論",,"離散構造とアルゴリズム","近代科学社","Vol. III",,"pp. 77-114",1994,
"渡辺 治","コンピュータ基礎理論ハンドブック I : アルゴリズムと複雑さ",,,"丸善",,,,1994,
"渡辺 治","NP型問題の近似解法の可能性について",,"オペレーションズ・リサーチ",,"Vol. 39","No. 2","pp. 105-111",1994,
"O. Watanabe","Test instance gereration for promised NP seaarch problems","Ninth Annual Structure in Complexity Theory Conference","Proceedings of the Ninth Annual Structure in Complexity Theory Conference, June 28-July 1, 1994, Amsterdam, the Netherlands","IEEE",,,"pp. 205-216",1994,
"Seinosuke Toda,Osamu Watanabe","Some structural analysis on the complexity of inverse functions",,"Mathematical Systems Theory","Mathematical Systems Theory",,"No. 26","pp. 203-214",1993,
"M. Ogiwara,T. Tierauf,S. Toda,O. Watanabe","On closure properties of #P in the context of Pfo # P","Eighth Annual Structure in Complexity Theory Conference","Proceedings of the Eighth Annual Structure in Complexity Theory Conference, May 18-21, 1993, San Diego, California","IEEE",,,"pp. 139-146",1993,
"J. Balcazar,J. Diaz,R. Gavalda,O. Watanabe","A note on the query complexity of learning DFA","3rd Workshop on Algorithmic Learning Theory (ALT'92)","Lecture Notes In Computer Science","Springer-Verlag","Vol. 743",,"pp. 53-62",1993,
"O. Watanabe","A view of structural complexity theory",,"Current trends in theoretical computer science","World Scientific",,,"pp. 451-468",1993,
"Ricard Gavalda,Osamu Watanabe","On the computational complexity of small descriptions",,"SIAM Journal of Computing",,"Vol. 22","No. 6","pp. 1257-1275",1993,
"R. Book,O. Watanabe","A view of structural complexity theory",,"Bulletin of the European Association for Theoretical Computer Science",,"Vol. 39",,"pp. 122-138",1993,
"OSAMU WATANABE","Kolgomorov Complexity and Computational Complexity",,,"Springer-Verlag",,,,1992,May
"渡辺治","計算可能性・計算の複雑さ入門",,"近代科学社","近代科学社",,,,1992,
"N. Abe,O. Watanabe","polonomially sparse variations and reducibility among prediction problems",,"IEICE Trans. Information and Systems","Institute of Electronics, Information and Communication Engineers","Vol. E75-D","No. 4","pp. 449--458",1992,
"O. Watanabe","Three layer network for identity mapping","コンプ研，電子情報通信学会","信学技報 COMP",,,,,1992,
"K. kurosawa,O. Watanabe","Computational and statistical indistinguishability","Algorithms and computation : Third International Symposium, ISAAC '92","Lecture notes in computer science","Springer-Verlag","Vol. 650",,"pp. 430-438",1992,
"OSAMU WATANABE","Relating equivalence and reducibility to sparse sets",,"SIAM Journal on Computing",,"Vol. 21","No. 3","pp. 521-539",1992,
"O. Watanabe,T. Ibaraki","Special Section on Theoretical Foundation of Computing",,,"IEICE",,,,1992,
"S. Toda,O. Watanabe","Polynomial time 1-turing reductions from #PH to #P",,"Theoretical Computer Science","Elsevier Science Publishers","Vol. 100","No. 1","pp. 205--221",1992,
"O. Watanabe","On polynomial-time one-truth-table reduccibility to sparse sets",,"Journal of Computer and System Sciences","Academic Press","Vol. 44","No. 3","pp. 500--516",1992,
"O. Watanabe","On the complexity of small description and related topics","Mathematical foundations of computer science 1992 : 17th International Symposium","Lecture notes in computer science",,"Vol. 629",,"pp. 82-94",1992,
"O. Watanabe","Kolmogorov Complexity: Theory and Relations to Computational Complexity",,,"Springer-Verlag",,,,1992,
"S. Tang,O. Watanabe","On polynomial -time turing and many-one completeness in PSPACE",,"Theoretical Computer Science","Elsevier Science Publishers","Vol. 97","No. 2","pp. 199-215",1992,
"L. Longpre,O. Watanabe","On symmetry of information and polynomial time invertibility","3rd International Symposium on Algorithms and Computation (ISAAC'92)","Third International Symposium, ISAAC'92 Nagoya, Japan, December 16?18, 1992 Proceedings","Springer Berlin Heidelberg","Vol. 650",,"pp. 410-419",1992,
"L. Hemachandra,M. Ogiwara,O. Watanabe","How hard are sparse sets ?","Seventh Annual Structure in Complexity Theory Conference","SProceedings of the Seventh Annual Structure in Complexity Theory Conference, June 22-25, 1992, Boston University, Boston, Massachusetts","IEEE",,,"pp. 222-238",1992,
"渡辺 治","一方向関数のお話",,"情報処理","社団法人情報処理学会","Vol. 32","No. 6","pp. 704-714",1991,
"O. Watanabe","On intractability of the class UP",,"Mathematical Systems Theory","Springer Verlag","Vol. 24",,"pp. 1-10",1991,
"O. Watanabe","A note on the p-isomorphism conjecture",,"Theoretical Computer Science","Elsevier Science Publishers","Vol. 83",,"pp. 337-343",1991,
"E. Allender,L. Hemachandra,M. Ogiwara,O. Watanabe","Relating equivalence and reducibility to sparse sets","6th Structure in Complexity Theory Conference","Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual","IEEE",,,"pp. 220--229",1991,
"渡辺 治","計算論的学習のお話",,"人工知能学会誌",,"Vol. 6","No. 5","pp. 641-650",1991,
"T. Koshiba,O. Watanabe","A note on the construction of decision trees","コンプ研，電子情報通信学会","信学技報 COMP",,,,,1991,
"R. Gavalda,O. Watanabe","On the computational complexity of small descriptions","6th Structure in Complexity Theory Conference","Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual","IEEE",,,"pp. 89 - 101",1991,
"M. Ogiwara,O. Watanabe","On polynomial time bounded truth -table reducibility of NP sets to sparse sets",,"SIAM Journal on Computing",,"Vol. 20",,"pp. 471-483",1991,
"O. Watanabe","A formal study of learning via queries","Automata, languages and programming : 17th international colloquium","Lecture notes in computer science","Springer-Verlag","Vol. 443",,"pp. 139-152",1990,
"M. Ogiwara,O. Watanabe","On polynomial time bounded truth-table reducibility of NP sets to sparse sets","22nd Annual ACM symposium on Theory of Computing (STOC'90)","Proceeding STOC '90 Proceedings of the twenty-second annual ACM symposium on Theory of computing","ACM",,,"pp. 457--467",1990,
"R. Gavalda,L. Torenvilet,J. Balcazar,O. Watanabe","Generalized Kolmogorov complexity in relativized separations","Mathematical Foundations of Computer Science (MFCS'90)","Lecture notes in computer science","Springer-Verlag","Vol. 452",,"pp. 269-276",1990,
"O. Watanabe","Structural analyses on the complexity of inverting functions","Algorithms : International Symposium SIGAL '90","Lecture notes in computer science",,"Vol. 450",,"pp. 31-38",1990,
"OSAMU WATANABE","Kolmogorov Complexity and degrees of tally sets(共著)",,"Information and Computation",,"Vol. 86",,"pp. 160-178",1990,
"S.Tang,O. Watanabe","On tally relativizations of BP-commplexity classes",,"SIAM Journal on Computing","Society for Industrial and Applied Mathematics","Vol. 18",,"pp. 449--462",1989,
"S. Tang,O. Watanabe","On polynomial-time turning and many-one completeness in PSPACE","4th Structure in Complexity Theory Conference","Proceegings, structure in complexity theory : fourth annual conference","IEEE",,,"pp. 15-23",1989,
"O. Watanabe","On one-way functions",,"Combinatorics, Computing and Complexity","Science Press",,,"pp. 98-131",1989,
"O. Watanabe","On 1-tt-sparseness of nondeterministic complexity classes","15th International Colloquium on Automata, Languages and Programming","Lecture Notes in Computer Science","Springer-Verlag","Vol. 317",,"pp. 697-709",1988,
"S. Tang,O. Watanabe","On tally relativizations of BP-complexity classes,","3rd Structure in Complexity Theory Conference","Proceedings, structure in complexity theory, third annual conference : June 14-17, 1988, Georgetown University, Washington, D.C.","IEEE",,,"pp. 10-18",1988,
"A. Allender,O. Watanabe","Kolmogorov complexity and degrees of tally sets","3rd Structure in Complexity Theory Conference","Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual","IEEE",,,"pp. 102-112",1988,
"R. Book,P. Orponen,D. Russo,Osamu Watanabe","Lowness properties of sets in the exponential-time hierarchy",,"SIAM Journal on Computing","Society for Industrial and Applied Mathematics","Vol. 17",,"pp. 504--516",1988,
"O. Watanabe","On hardness of one-way functions",,"Information Processing Letters","Elsevier Science Publishers","Vol. 27",,"pp. 151--157",1988,