論文

• 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, Sept. 2019.
• Suguru Tamaki, Osamu Watanabe. Local Restrictions from the Furst-Saxe-Sipser Paper, Theory of Computing Systems, Vol. 60, No. 1, Page 20-32, Jan. 2017.
• Akinori Kawachi, Benjamin Rossman, Osamu Watanabe. The Query Complexity of Witness Finding, Theory of Computing Systems, Vol. 61, No. 2, pp. 305–321, Sept. 2016.
• Daniel Kane, Osamu Watanabe. A short implicant of a CNF formula with many satisfying assignments, Algorithmica, Springer US, 76, 4, pp. 1203-1223, Feb. 2016.
• 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, Sept. 2015.
• Osamu Watanabe. Message passing algorithms for MLS-3LIN problem, Algorithmica, Vol. 66, No. 4, pp. 848-868, Aug. 2013.
• 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, June 2013.
• O. Watanabe. Introduction of the ELC project, ELC Tokyo Complexity Workshop, Mar. 2013.
• O. Watanabe. Perturbed k-linear-equation problems, Workshop at IIT Kanpur, Aug. 2012.
• 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, Mar. 2012.
• Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe. Propagation connectivity of random hypergraphs, The Electronic Journal of Combinatorics, Vol. 19, pp. 1-25, 2012.
• 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, Aug. 2011.
• 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, June 2011.
• Toshiya Itoh, Osamu Watanabe. Weighted Random Popular Matchings, Random Structures and Algorithms, Wiley, Vol. 37, No. 4, pp. 477-494, Dec. 2010.
• 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, Apr. 2010.
• OSAMU WATANABE, Masaki Yamamoto. Average-case analysis for the MAX-2SAT problem, Theoretical Computer Science, Springer, Vol. 411, No. 16-18, pp. 1685--1697, Mar. 2010.
• 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, Jan. 2010.
• 渡辺 治. 理論研究の役割（学会５０周年企画，情報処理技術の未来地図）, 情報処理学会誌, Vol. 51, No. 5, 2010.
• 渡辺 治. 情報科学技術は人類の言葉, 情報科学教育学会全国大会, 2010.
• Mikael Onsjö, OSAMU WATANABE. Finding most likely solutions, Theory of Computing Systems, Springer, Vol. 45, No. 4, pp. 926-942, Nov. 2009.
• Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe. Scale free interval graphs, Theoretical Computer Science, vol. 410, no. 45, pp. 4588-4600, Oct. 2009.
• 飯田勝吉, 新里卓史, 伊東利哉, 渡辺治. キャンパス共通認証認可システムの構築と運用, 電子情報通信学会, Vol. J92-B, No. 10, pp. 1554-1565, Oct. 2009.
• 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, Apr. 2008.
• Thomas Hofmeister, Uwe Schoning, Rainer Schuler, Osamu Watanabe. Randomized algorithms for 3-SAT, Theoretical Computer Science, Vol. 40, pp. 249-262, Jan. 2007.
• JinYi Cai, Osamu Watanabe. Random access to advice strings and collapsing result, Algorithmica, Vol. 45, No. 1, pp. 43-57, 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.
• Osamu Watanabe. Pseudo expectation: A tool for analyzing local search algorithms, Progress of Theoretical Physics, Supplement, No. 157, pp. 338-344, Apr. 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.
• 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.
• S. Aida, M. Crasmaru, K. Regan, O. Watanabe. Games with a uniqueness property, Theory of Comput. Systems, Vol. 37, pp. 29-47, 2003.
• 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.
• 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.
• 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.
• 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.
• OSAMU WATANABE. Simple sampling techniques for discovery science, IEICE Trans. Information and Systems, Vol. E83-D, No. 1, pp. 19-26, 2000.
• 望月 厚, 元木 光雄, 渡辺 治. ３充足可能性判定問題３ＳＡTの正例題生成手法の解析, 情報処理学会論文誌, Vol. 39, No. 6, pp. 1850-1857, 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.
• 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.
• 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.
• Luc Longpre, Osamu Watanabe. On Symmetry of Information and Polynomial Time Invertibility, Information and Computation, Vol. 121, No. 1, pp. 14-22, 1995.
• 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.
• 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.
• Ricard Gavalda, Osamu Watanabe. On the computational complexity of small descriptions, SIAM Journal of Computing, Vol. 22, No. 6, pp. 1257-1275, 1993.
• 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.
• OSAMU WATANABE. Relating equivalence and reducibility to sparse sets, SIAM Journal on Computing, Vol. 21, No. 3, pp. 521-539, 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• O. Watanabe. On the computational complexity of small descriptions, 17th Int'l Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS, Vol. 629, pp. 82-94, 1987.
• OSAMU WATANABE. A comparison of polynomial time completeness notions, Theoretical Computer Science, Vol. 54, pp. 249-265, 1987.
• 渡辺 治. 確率的アルゴリズムにおける効率・正解率間のトレードオフ関係について, 情報処理学会論文誌, 情報処理学会, Vol. 27, pp. 485--491, 1986.
• OSAMU WATANABE. On one-one polynomial time equivalence relations, Theoretical Computer Science, pp. 38, 1985.
• O. WATANABE. On one-one polynomial trade off problem on on-line probabilistic turing machines, Theoretical Computer Science, Elsevier Science Publishers, Vol. 38, pp. 157-165, 1985.
• Osamu Watanabe. The time-precision trade off problem on on-line probabilistic turing machines, Theoretical Computer Science, Vol. 24, pp. 105-117, 1983.
• O. Watanabe. A fast algorithm for finding all shortest paths, Information Processing Letters, Vol. 13, pp. 1-3, 1981.
• O. Watanabe. Another application of recursion introduction, Information Processing Letters, Vol. 10, pp. 116-119, Jan. 1980.

著書

• 渡辺 治. コンピュータサイエンス －計算を通して世界を観るー, 丸善サイエンスパレット, Sept. 2015.
• 渡辺 治. 今度こそわかるＰ≠ＮＰ予想, 講談社サイエンティフィク, 2014.
• OSAMU WATANABE. Randomness in Algorithms, Randomness through Computation, World Scientific, pp. 297--308, Feb. 2011.
• 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.
• 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.
• 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, Oct. 2009.
• 渡辺治, 北野晃朗, 木村泰紀, 谷口雅治. 数学の言葉と論理, 朝倉書店, Sept. 2008.
• Michael Sipser, 太田和夫, 阿部正幸, 植田広樹, 田中圭介, 藤岡淳, 渡辺治. 計算理論の基礎 [原著第2版] 1. オートマトンと言語, 共立出版, May 2008.
• Michael Sipser, 太田和夫, 阿部正幸, 植田広樹, 田中圭介, 藤岡淳, 渡辺治. 計算理論の基礎 [原著第2版] 3. 複雑さの理論, 共立出版, May 2008.
• Michael Sipser, 太田和夫, 阿部正幸, 植田広樹, 田中圭介, 藤岡淳, 渡辺治. 計算理論の基礎 [原著第2版] 2. 計算可能性の理論, 共立出版, May 2008.
• 金森 敬文, 畑埜 晃平, 渡辺 治. ブースティング --- 学習アルゴリズムの設計技法, 森北出版, 2006.
• 松田裕幸, 渡辺治. スーパーコン甲子園, 日本評論社, June 2005.
• A. Sharma, O Watanabe. Algorithmic Learning Theory, Elsevier, 2002.
• 渡辺治. 教養としてのコンピュータ・サイエンス, サイエンス社, サイエンス社, 2001.
• A. Sharma, O Watanabe. Special Issue on Algorithmic Learning Theory, Elsevier, 2001.
• 太田和夫, 渡辺治. 計算理論の基礎, 共立出版, Apr. 2000.
• O. Watanabe, T. Yokomori. Proc. 10th International Conference on Algorithmic Learning Theory, Springer-Verlag, 1999.
• 太田和夫, 黒澤馨, 渡辺治. 情報セキュリtィの科学, 講談社ブルーバックス, 講談社ブルーバックス, 1995.
• 太田 和夫, 黒澤 肇, 渡辺 治. 情報セキュリティーの科学： マジック・プロトコルへの招待, 講談社ブルーバックス, 1995.
• 渡辺 治. コンピュータ基礎理論ハンドブック I : アルゴリズムと複雑さ, 丸善, 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.
• OSAMU WATANABE. Kolgomorov Complexity and Computational Complexity, Springer-Verlag, May 1992.
• 渡辺治. 計算可能性・計算の複雑さ入門, 近代科学社, 近代科学社, 1992.
• O. Watanabe, T. Ibaraki. Special Section on Theoretical Foundation of Computing, IEICE, 1992.
• O. Watanabe. Kolmogorov Complexity: Theory and Relations to Computational Complexity, Springer-Verlag, 1992.

国際会議発表 (査読有り)

• 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, Jan. 2016.
• 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, Oct. 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, Dec. 2014.
• 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.
• 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.
• 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.
• 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, Jan. 2012.
• 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.
• 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.
• 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, June 2011.
• 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, Aug. 2010.
• 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), July 2010.
• 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, Feb. 2010.
• Madhusuden Agrawal, OSAMU WATANABE. One-way functions and the Berman-Hartmanis conjecture, 24th Conference on Computational Complexity, July 2009.
• 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, June 2008.
• 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, June 2007.
• 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.
• 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.
• 渡辺治. Computational Complexity and Its Applications, Theory and Applications of Models of Computation (TAMC05), 2005.
• 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.
• J.Y. Cai, O. Watanabe. Relativized collapsing results under stringent oracle access, 第１回情報科学技術フォーラム, 情報技術レターズ, 電子情報通信学会, Vol. 1, No. 1, pp. 1-2, Sept. 2002.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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. 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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 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.
• O. Watanabe. Polynomial time reducibility to a set of small density, 2nd Structure in Complexity Theory Conference, Proceedings : structure in complexity theory : second annual conference, June 16-19, 1987, Cornell University, Ithaca, NY, IEEE, pp. 138-146, 1987.
• R. Book, P. Orponen, D. Russo, O. Watanabe. On exponential lowness, 13th International Colloquium on Automata, Languages and Programming (ICALP'86), Lecture Notes in Computer Science, Vol. 226, pp. 40-49, 1986.
• K. Ko, U. Schoning, P. Orponen, O. Watanabe. What is a hard instance of a computational problem ?, 1st Structure in Complexity Theory Conference, Lecture Notes in Computer Science, Vol. 223, pp. 197-217, 1986.

国内会議発表 (査読有り)

• 石畑 清, 大岩 元, 角田 博保, 清水 謙多郎, 玉井 哲雄, 長崎 等, 中里 秀則, 中谷 多哉子, 疋田 輝雄, 三浦 孝夫, 箕原 辰夫, 和田 耕一, 渡辺 治. 理工系情報学科の授業内容分布のシラバスによる調査（中間報告）, 情報教育シンポジウム, 情報教育シンポジウム, 情報処理学会 コンピュータと教育研究会, Aug. 2010.
• 副島佑介, 岸本 章宏, 渡辺治. モンテカルロ木探索のRoot並列化とコンピュータ囲碁での有効性について, 第14回ゲーム・プログラミングワークショップ, Nov. 2009.
• 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.
• K. Hatano, O. Watanabe. Learning r-of-k functions by boosting, コンプ研，電子情報通信学会, 信学技報 COMP, No. 22, pp. 27-32, 2004.
• 新倉 康明, J. Schneider, 渡辺 治. 単純な規則で表されるマルコフ過程の近似解析手法, アルゴリズム研，情報処理学会, 情処研報 AL, No. 94, pp. 73-80, 2004.
• O. Watanabe. P vs. NP and P vs. PSPACE, 科研費基盤（Ｃ）企画研究，研究集会, 2003.
• 渡辺 治. LDPCの複合化のためのランダム局所探索アルゴリズムの解析, 北陸先端大学院大学 情報科学研究科セミナー, 2002.
• J. Balcazar, 戴 陽, O. Watanabe. Provably fast trainning algorithms for support vector machines, コンプ研，電子情報通信学会, 信学技報 COMP, No. 66, pp. 25-32, 2002.
• 渡辺 治. ある制約式充足問題群の解法について, OR学会関西支部 OR若手研究者の会、離散アルゴリズム研究部会, 2002.
• K. Amano, P. Vitanyi, O. Watanabe. On the length of the monopolist game, コンプ研，電子情報通信学会, 信学技報 COMP, No. 62, pp. 41-48, 2000.
• O. Watanabe. Three layer network for identity mapping, コンプ研，電子情報通信学会, 信学技報 COMP, 1992.
• T. Koshiba, O. Watanabe. A note on the construction of decision trees, コンプ研，電子情報通信学会, 信学技報 COMP, 1991.

国際会議発表 (査読なし・不明)

• 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, May 2016.
• D. Kane, O. Watanabe. Implicant size of a CNF formula with many satisfying assignments, コンプ研，電子情報通信学会, 信学技報 COMP2014-31, Oct. 2014.
• 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，中国科学院，北京, Oct. 2014.
• 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, May 2013.
• 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, Oct. 2009.
• Takeya Shigezumi, Naoto Miyoshi, Ryuhei Uehara, Osamu Watanabe. Scale free interval graphs, The First Asian Association for Algorithms and Computation Annual Meeting (AAAC08), Apr. 2008.
• 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, Oct. 2005.
• M. Onsjoe, O. Watanabe. A message passing algorithm for the bisection problem, 日韓ワークショップ, 2005.
• 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.
• O. Watanabe. Pseudo expectation: A tool for analyzing local search algorithms, Optimization algorithms and quantum disordered systems, 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.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.
• 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.
• Kyoichi Okamoto, Osamu Watanabe. Deterministic application of Grover's quantum search algorithm, アルゴリズム研，情報処理学会, 情処研報 AL, 2000.
• 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.

国内会議発表 (査読なし・不明)

• Tong Qin, Osamu Watanabe. An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem, COMP, 信学技報, vol. 117, no. 269, pp. 5-12, Oct. 2017.
• Osamu Watanabe. Sublinear space complexity, Workshop on Connection between Algorithm Design and Complexity Theory, Sept. 2016.  公式リンク  
  
• 渡辺 治. この本！ おすすめします コンピューターサイエンスを教養に, 情報管理, 国立研究開発法人 科学技術振興機構, Vol. 59, No. 1, May 2016.
• 渡辺 治. 新学術領域「計算限界解明」の研究紹介, NII 情報系 Winter Festa, 2015.
• 渡辺 治. 計算限界への挑戦：Ｐ＝ＮＰの世界を目指して, 第26回RAMPシンポジウム，ＯＲ学会, Oct. 2014.
• ケイン ダニエル, 渡辺 治. 多くの充足解を持つ和積形論理式のインプリカントの大きさについて, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 一般社団法人電子情報通信学会, Vol. 114, No. 238, Sept. 2014.
• 渡辺 治. スーパーコン : 高校生・高専生の電脳甲子園(<特集>若い力:高校生の問題解決), オペレーションズ・リサーチ : 経営の科学, 公益社団法人日本オペレーションズ・リサーチ学会, Vol. 59, No. 6, May 2014.
• O. Watanabe. Max k-linear equation problem, 力学系と計算，京都大学, Jan. 2014.
• 渡辺 治. 環境適用型アルゴリズム, CREST特定課題調査「ビッグデーター時代に向けた革新的アルゴリズム基盤」シンポジウム，京都リサーチパーク, Jan. 2014.
• 渡辺 治. 「多面的アプローチの統合による計算限界の解明」について, JST ERATO 合同 WS，日本未来館, Jan. 2014.
• 渡辺 治. 計算複雑さの理論とその進展, 東北大学数学教室談話会, Dec. 2013.
• 渡辺 治. 計算限界解明：なぜ限界を？＆なぜ今？, FIT13，鳥取大学, Sept. 2013.
• 渡辺 治. 計算限界への挑戦：Ｐ＝ＮＰの世界を目指して, e-サイエンスシンポジウム，京都大学, June 2013.
• 河内 亮周, ロスマン ベンジャミン, 渡辺 治. NP-解探索における質問計算量について(一般), 電子情報通信学会技術研究報告. COMP, コンピュテーション, 一般社団法人電子情報通信学会, Vol. 113, No. 50, Apr. 2013.
• 河内 亮周, ロスマン ベンジャミン, 渡辺 治. NP-解探索における質問計算量について, 研究報告アルゴリズム（AL）, 一般社団法人情報処理学会, Vol. 2013, No. 7, Apr. 2013.
• 遊佐 俊彦, 渡辺 治. DS-1-5 正規化圧縮距離の妥当性解析(DS-1.COMP学生シンポジウム,シンポジウムセッション), 電子情報通信学会総合大会講演論文集, 一般社団法人電子情報通信学会, Vol. 2013, No. 1, Feb. 2013.
• 山口 裕生, 渡辺 治. べき則グラフ上での対立する噂の拡散の解析 : 二種類の次数の頂点からなるグラフの場合(一般), 電子情報通信学会技術研究報告. COMP, コンピュテーション, 一般社団法人電子情報通信学会, Vol. 112, No. 340, Nov. 2012.
• 渡辺 治. 計算複雑さへの招待(1):基本+平均時計算複雑さ(特別企画), 電子情報通信学会技術研究報告. COMP, コンピュテーション, 一般社団法人電子情報通信学会, Vol. 112, No. 340, Nov. 2012.
• 渡辺 治. [招待講演]新学術領域「計算限界解明」発足にあたって, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 一般社団法人電子情報通信学会, Vol. 112, No. 199, July 2012.
• 渡辺 治. 計算複雑さの理論 : 我々は何を研究しているのか?, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 一般社団法人電子情報通信学会, Vol. 111, No. 256, Sept. 2011.
• Yoshinori Aono, Manindra Agrawal, Osamu Watanabe. On Coppersmith's technique and its limit, 電子情報通信学会2010年総合大会, シンポジウム DS-1 ＣＯＭＰ学生シンポジウム, Mar. 2010.
• 副島佑介, 岸本章宏, 渡辺治. モンテカルロ木探索のroot並列化とコンピュータ囲碁での有効性について, 第14回ゲーム・プログラミングワークショップ, pp. 27--33, Nov. 2009.
• Mikael Onsjö, OSAMU WATANABE. Implementation of a bit-parallel approximate string matching algorithm, 情報処理学会アルゴリズム研究会, Information Processing Society of Japan, Vol. AL-124, No. 3, Mar. 2009.
• Takeya Shigezumi, Naoto Miyoshi, Ryuhei Uehara, Osamu Watanabe. Scale free interval graphs, 電子情報通信学会2008年総合大会, Mar. 2008.
• 新里卓史, 飯田勝吉, 植松友彦, 渡辺治. 東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構, 電子情報通信学会2008年総合大会, 電子情報通信学会, BS‐8‐3, Mar. 2008.
• 新里卓史, 飯田勝吉, 植松友彦, 渡辺治. 東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構の設計と実装, 電子情報通信学会, Vol. 107, No. 449, pp. 45-50, Jan. 2008.
• Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe. Scale Free Interval Graphs, 東京工業大学グローバル COE 「計算世界観の深化と展開」発足シンポジウム, Dec. 2007.
• Osamu Watanabe. Complexity of finding most likely solutions, コンプ研,電子情報通信学会, 信学技報 COMP, Oct. 2007.
• 伊東利哉, 渡辺治. 重みつき乱択最適選好マッチング, コンプ研,電子情報通信学会, 信学技報 COMP, Oct. 2007.
• Takeya Shigezumi, 上原隆平, Osamu Watanabe. Do interval graphs dream of scale-free network?, 2007年夏のLAシンポジウム, July 2007.

その他の論文・著書など

• 渡辺 治, 遠藤 敏夫. スーパーコンピューティングコンテスト・2013, 数学セミナー, 日本評論社, Vol. 53, No. 1, pp. 50-55, 2014.
• 渡辺 治. P≠NP予想って？, 数学セミナー, 日本評論社, Vol. 52, No. 12, pp. 8-12, 2013.
• 渡辺 治. P≠NP予想最前線, 数学セミナー, 日本評論社, Vol. 52, No. 12, pp. 8-43, 2013.
• 渡辺 治. 計算複雑さの研究って?, コンピュータソフトウェア, Japan Society for Software Science and Technology, Vol. 29, No. 2, Mar. 2012.
• 渡辺治, 松田裕幸. スパコンをぶん回せ - スーパーコンピューティングコンテスト・2008, 数学セミナー, Vol. 47, No. 12, pp. 41-45, Dec. 2008.
• 渡辺 治. でたらめさを利用した計算, 科学, 岩波書店, Vol. 10, 2007.
• J. Cai, O. Watanabe. Stringent relativization: a new approach for studying complexity classes, SIGACT news, Vol. 37, No. #140, Dec. 2006.
• 渡辺 治. 教養としてのコンピュータ・サイエンス教育――東京工業大学での試み, 情報処理, Vol. 47, No. 12, pp. 1372-1377, 2006.
• 渡辺 治. ランダムネスの面白さ, 数理科学, サイエンス社, No. 9, 2006.
• 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.
• 渡辺 治. ブースティング技法のアルゴリズム的考察, 日本神経回路学会誌, Vol. 9, No. 3, pp. 196-203, 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.
• 渡辺 治. コンピュータサイエンスのための単純かつ効率的なサンプリング技法, 発見科学とデータマイニング, 共立出版, pp. 86-96, 2000.
• 渡辺 治. 計算を究める−アルゴリズムと計算の複雑さの研究, IT革命最前線：情報処理学会創立４０周年記念出版, 情報処理学会, pp. 201-209, 2000.
• 根上 生也, 松井 知己, 渡辺 治. Web 鼎談, 数学セミナー, 日本評論社, Vol. 99-00, No. 4-3, 1999.
• T. Motoki, 渡辺 治. Test instance generators for SAT, 1997.
• 渡辺 治. 東工大スーパーコンピュータコンテスト, 数学セミナー, 日本評論社, Vol. 36, pp. 67-71, 1997.
• 渡辺 治. 東工大スーパーコンピュータコンテスト, 数学セミナー, 日本評論社, Vol. 34, pp. 34-41, 1995.
• 渡辺 治. 一方向関数の基礎理論, 離散構造とアルゴリズム, 近代科学社, Vol. III, pp. 77-114, 1994.
• 渡辺 治. NP型問題の近似解法の可能性について, オペレーションズ・リサーチ, Vol. 39, No. 2, pp. 105-111, 1994.
• O. Watanabe. A view of structural complexity theory, Current trends in theoretical computer science, World Scientific, pp. 451-468, 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.
• 渡辺 治. 一方向関数のお話, 情報処理, 社団法人情報処理学会, Vol. 32, No. 6, pp. 704-714, 1991.
• 渡辺 治. 計算論的学習のお話, 人工知能学会誌, Vol. 6, No. 5, pp. 641-650, 1991.
• O. Watanabe. On one-way functions, Combinatorics, Computing and Complexity, Science Press, pp. 98-131, 1989.
• 渡辺 治. 確率的アルゴリズム, 情報処理学会誌, Vol. 24, pp. 372-377, 1983.

学位論文

• On the Structure of Intractable Complexity Classes,  Thesis,  Doctor of Engineering,  Tokyo Institute of Technology,  1987/05/31,   

[ BibTeX 形式で保存 ]    [ 論文・著書をCSV形式で保存 ]    [ 特許をCSV形式で保存 ]