Publication List

Osamu Watanabe (Last Update 2017.5.12)

Refer to Tokyo Tech Research Repostitory for the other publications.

Journal Papers

  1. Daniel Kane and Osamu Watanabe, A short implicant of a CNF formula with many satisfying assignments, Algorithmica, 76(4): 1203--1223, 2016. 10.1007/s00453-016-0125-z
  2. Johannes Kobler, Sebastian Kuhnert, and Osamu Watanabe:, Interval graph representation with given interval and intersection lengths, J. Discrete Algorithms, 34:108--117, 2015. 10.1016/j.jda.2015.05.011
  3. Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe, Is Valiant-Vazirani's isolation probability improvable?, Computational Complexity, 22(2): 345--383, 2013. 10.1007/s00037-013-0059-7
  4. Osamu Watanabe, Message passing algorithms for MLS-3LIN problem, Algorithmica, 66(4): 848--868, 2014. 10.1007/s00453-013-9762-7
  5. A. Kawachi, H. Tanaka, and O. Watanabe, Estimating the Gowers norm of modulo functions over prime fields, IEICE Transactions on Information and Systems, E95-D(3): 755--762, 2012.
  6. A. Coja-Oghlan, M. Onsjo, and O. Watanabe, Propagation connectivity of random hypergraphs, The Electronic Journal of Combinatorics, 19(P17): 1--25, 2012.
  7. T. Shigezumi, Y. Uno, and O. Watanabe, A new model for a scale-free hierarchical structure of isolated clique, J. Graph Algorithms Appl., 15(5): 661-682, 2011.
  8. T. Ando, Y. Kabashima, H. Takahashi, .O. Watanabe, M. Yamamoto, Spectral analysis of random sparse matrices, IEICE Transactions on Information and Systems, E94-D(6): 1247-1256, 2011.
  9. Y. Soejima, A. Kishimoto, and O. Watanabe, Evaluating root parallelization in Go, IEEE Transactions on Computational Intelligence and AI in Games, 2(4): 278--287, 2010.
  10. Y. Kabashima, H. Takahashi and O. Watanabe, Cavity approach to the first eigenvalue problem in a family of symmetric random sparse matrices, J. Phys. Conf. Ser., 233, 012001(11pages), 2010.
  11. T. Itoh and O. Watanabe, Weighted random popular matchings, Random Struct. Algorithms, 37(4): 477--494, 2010.
  12. O. Watanabe and M. Yamamoto, Average-case analysis for the MAX-2SAT problem, Theoretical Computer Science, 411(16-18): 1685--1697, 2010.
  13. E. Hemaspaandra, L. Hemaspaandra, T. Tantau, and O. Watanabe, On the complexity of kings, Theoretical Computer Science, 411(4-5): 783--798, 2010.
  14. Japanese record, omitted.
  15. N. Miyoshi, T. Shigezumi, R. Uehara, and O. Watanabe, Scale free interval graphs, Theoretical Computer Science, 410(45): 4588--4600, 2009.
  16. Mikael Onsjoe and O. Watanbae, Finding most likely solutions, Theory of Computing Systems, 45(4): 926--942, 2009.
  17. J.L. Balcazar, Y. Dai, J. Tanaka, and O. Watanabe, Provably fast training algorithms for support vector machines, Theory Computing Systems, 42(4): 568--595, 2008.
  18. T. Hofmeister, U. Schoening, R. Schuler, and O. Watanabe, Randomized algorithms for 3-SAT, Theory of Comput. Systems, 40: 249--262, 2007.
  19. J.Y. Cai and O. Watanabe, Random access to advice strings and collapsing result, Algorithmica, 45(1): 43--57, 2006.
  20. S. Balaji, H.M. Mahmoud, and O. Watanabe, Distributions in the Ehrenfest process, Statistics and Probability Letters, 76(7): 666-674, 2006.
  21. O.Watanabe, Sequential sampling techniques for algorithmic learning theory, Theoretical Computer Science, 348(1,2): 3--14, 2005.
  22. O.Watanabe, Pseudo expectation: A tool for analyzing local search algorithms, Progress of Theoretical Physics, Supplement, (157): 338--344, 2005.
  23. R. Kato and O. Watanabe, Substring search and repeat search using factor oracles, Information Processing Letters, 93(6): 269-274, 2005.
  24. J. Cai and O. Watanabe, On proving circuit lower bounds against the polynomial-time hierarchy, SIAM Journal on Computing, 33(4): 984--1009, 2004.
  25. J. Cai and O. Watanabe, Relativized collapsing between BPP and PH under stringent oracle access, Information Processing Letters, 90: 147--154, 2004.
  26. S. Aida, M. Crasmaru, K. Regan, and O. Watanabe, Games with a uniqueness property, Theory of Comput. Systems, 37: 29--47, 2003.
  27. S. Aida, R. Schuler, T. Tsukiji and O. Watanabe, The difference between polynominal-time many-one and truth-table reducibilities on distributional problems , Theory of Comput. Systems, 35: 449--463, 2002.
  28. C. Domingo, R. Gavalda, and O. Watanabe, Adaptive sampling methods for scaling up knowledge discovery algorithms, Data Mining and Knowledge Discovery, 6(2): 131--152, 2002.
  29. W. Lindner, R. Schuler, and O. Watanabe, Resource-bounded measure and learnability, Theory of Comput. Systems, 33: 151--170, 2000.
  30. J. Kobler and O.Watanabe, New collapse consequence of NP having small circuits, SIAM Journal on Computing, 28(1): 311--324, 1998.
  31. L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe, Boolean operations, joins and the extended low hierarchy, Theoretical Computer Science, 205(1-2): 317--327, 1998.
  32. Japanese record, omitted.
  33. C. Domingo, T. Tsukiji, and O. Watanabe, Partial Occam's razor its applications, Information Processing Letters, 64: 179--185, 1997.
  34. L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe, Pollynomial-time multi-selectivity, J. of Universal Computer Science, 3(3): 197--229, 1997.
  35. H .C. Lau and O. Watanabe, Randomized approximation of the constraint satisfation problem, Nodric Journal of Computing, 3: 405--424, 1996.
  36. J. Balcazar, J. Diaz, R. Gavalda, and O. Watanabe, An optimal parallel algorithm for learning DFA, Journal of Universal Computer Science, , 1996.
  37. R .Book and O. Watanabe, On random hard sets for NP, Information and Computation, 125: 70--76, 1996.
  38. T. Thierauf, S. Toda, and O. Watanabe, On sets bounded truth-table reducible to P-selective sets, Theoretical Informatics and Applications, 30(2): 135--154, 1996.
  39. M. Ogiwara, T. Thierauf, S. Toda, and O. Watanabe, On closure properties of #P in the context of PFo#P, Journal of Computer and System Science, 53(2): 171--179, 1996.
  40. L. Longpre and O. Watanabe, On symmetry of information and polynomial time invertibility, Information and Computation, 121(1): 14--22, 1995.
  41. R. Rao, J. Rothe, and O. Watanabe, Upward separation for FewP and related classes, Information Processing Letters, 52(4): 175--180, 1994.
  42. T. Thierauf, S. Toda, and O. Watanabe, On closure properties of GapP, Computational Complexity, 4: 242--261, 1994.
  43. J. Balcazar, J. Diaz, R. Gavalda, and O. Watanabe, The query complexity of learning DFA, New Generation Computing, 12: 337--358, 1994.
  44. R. Gavalda and O. Watanabe, Structural analysis of polynomial time query learnability, Mathematical Systems Theory, 27: 231--256, 1994.
  45. O. Watanabe, A framework for polynomial time query learnability, Mathematical Systems Theory, 27: 211--229, 1994.
  46. P. Orponen, K. Ko, U. Schoning, and O. Watanabe, Instance Commplexity, Journal of the Association for Computing Machinery, 41(1): 96--121, 1994.
  47. R. Gavalda and O. Watanabe, On the computational complexity of small descriptions, SIAM Journal on Computing, 22(6): 1257--1275, 1993.
  48. S. Toda and O. Watanabe, Some structural analysis on the complexity of inverse functions, Mathematical Systems Theory, 26: 203--214, 1993.
  49. N. Abe and O. Watanabe, polonomially sparse variations and reducibility among prediction problems, IEICE Trans. Information and Systems, E75-D(4): 449--458, 1992.
  50. E..Allender, L. Hemachandra, M. Ogiwara, and O. Watanabe, Relating equivalence and reducibility to sparse sets, SIAM Journal on Computing, 21(3): 521--539, 1992.
  51. S. Toda and O. Watanabe, Polynomial time 1-turing reductions from #PH to #P, Theoretical Computer Science, 100(1): 205--221, 1992.
  52. S. Tang and O. Watanabe, On polynomial -time turing and many-one completeness in PSPACE, Theoretical Computer Science, 97(2): 199--215, 1992.
  53. O. Watanabe, On polynomial-time one-truth-table reduccibility to sparse sets, Journal of Computer and System Science, 44(3): 500--516, 1992.
  54. O. Watanabe, On intractability of the class UP, Mathematical Systems Theory, 24: 1--10, 1991.
  55. O. Watanabe, A note on the p-isomorphism conjecture, Theoretical Computer Science, 83: 337--343, 1991.
  56. M. Ogiwara and O. Watanabe, On polynomial time bounded truth -table reducibility of NP sets to sparse sets, SIAM Journal on Computing, 20: 471--483, 1991.
  57. A. Allender and O. Watanabe, Kolmogorov complexity and degrees of tally sets , Information and Computation, 86: 160--178, 1990.
  58. S.Tang and O.Watanabe, On tally relativizations of BP-commplexity classes, SIAM Journal on Computing, 18: 449--462, 1989.
  59. R. Book, P. Orponen, D. Russo, and O. Watanabe, Lowness properties of sets in the exponential-time hierarchy, SIAM Journal on Computing, 17: 504--516, 1988.
  60. O. Watanabe, On hardness of one-way functions, Information Processing Letters, 27: 151--157, 1988.
  61. O. Watanabe, A Comparison of polynomial time completeness notions, Theoretical Computer Science, 54: 249--265, 1987.
  62. Japanese record, omitted.
  63. O. Watanabe, On one-one polynomial trade off problem on on-line probabilistic turing machines, Theoretical Computer Science, 38: 157--165, 1985.
  64. O. Watanabe, The time-precision trade off problem on on-line probabilistic turing machines, Theoretical Computer Science, 24: 105--117, 1983.
  65. O. Watanabe, A fast algorithm for finding all shortest paths, Information Processing Letters, 13: 1--3, 1981.
  66. O. Watanabe, Another application of recursion introduction, Information Processing Letters, 10: 116--119, 1980.

Conference Papers (Refereed)

  1. Shuichi Hirahara and Osamu Watanabe, Limits of minimum circuit size problem as oracle, Proc. of the 31st Conference on Computational Complexity, LIPIcs 18: 18:1--18:20, 2016. 10.4230/LIPIcs.CCC.2016.18
  2. Linus Hermannson, Fredrik Johansson, and Osamu Watanabe, Generalized shortest path kernel on graphs, Proc. of the 18th International Conference on Discovery Science (DS 2015), LNAI 9356: 1?8., 2015. 10.1007/978-3-319-24282-8_8
  3. Daniel M. Kane and Osamu Watanabe, A short implicant of a CNF formula with many satisfying assignments, Proc. of the 25th Sympos. on Algoerithms and Computation (ISAAC'14), LNCS 8889:273--284, 2014. 10.1007/978-3-319-13075-0_22
  4. T. Asano, D.G. Kirkpatrick, K. Nakagawa, and O. Watanabe, O(sqrt(n))-space and polynomial-time algorithm for planar directed graph reachability, Proc. of the 39th Mathematical Foundations of Computer Science (MFCS'14), LNCS 8635, 45--56, 2014. 10.1007/978-3-662-44465-8_5
  5. T. Imai, K. Nakagawa, A. Pavan, N.V. Vinodchandran, and O. 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), IEEE 277--286, 2013. 10.1109/CCC.2013.35
  6. J. Koebler, S. Kuhnert, and O. Watanabe, Interval graphg representation with given interval and intersection lengths, Proc. of the 23rd International Symposium on Algorithms and Computation (ISAAC'12), LNCS 7676 :517--526, 2012.
  7. H. Dell, V. Kabanets, D. vanMelkebeek, O. Watanabe, Is Valiant-Vazirani's isolation probability improvable?, Proc. of the 27th Conference on Computational Complexity (CCC'12), IEEE 10--20, 2012.
  8. Y. Aono, M. Agrawal, T. Satoh, O. Watanabe, On the optimality of lattices for the Coppersmith technique, 17th Australasian Conference on Information Security and Privacy (ACISP), 376--389, 2012.
  9. O. Watanabe, Message passing algorithms for MLS-3LIN problem, Proc. of the 9th Meeting on Analytic Algorithmics and Combinatrics (ANALCO'12), SIAM 68--85, 2012.
  10. Y. Kobayashi, A. Kishimoto, and O. Watanabe, Evaluations of hash distributed A* in optimal sequence alignment, Proc. of the 29th International Joint Conference on Artificial Intelligence (IJCAI'11), AAAI 584--590, 2011.
  11. Japanese record, omitted.
  12. A. Coja-Oghlan, M. Onsjo, and O. Watanabe, Propagation connectivity of random hypergraphs, Proc. 14th Intl. Workshop on Randomization and Computation (RANDOM'10), LNCS 6302: 490--503, 2010.
  13. T. Shigezumi, Y. Uno, and O. Watanabe, A new model for a scale-free hierarchical structure of isolated cliques, Proc. of 4th Workshop on Algorithms and Computation (WALCOM'10), LNCS 5942: 216--227, 2010.
  14. M. Agrawal and O. Watanabe, One-way functions and the Berman-Hartmanis conjecture, Proc. of 24th Conference on Computational Complexity (CCC'09), IEEE 194--202, 2009.
  15. T. Shigezumi, N. Miyoshi, R. Uehara, and O. Watanabe, Scale free interval graphs, Proc. of 4th International Conference on Algorithmic Aspects in Information and Management (AAIM'08), LNCS 5034: 292--303, 2008.
  16. E. Hemaspaandra, L. Hemaspaandra, T. Tantau, and O. Watanabe, On the complexity of kings, Proc. 16th International Symposium on Fundamentals of Computation Theory (FCT'07), LNCS 4639:328--340, 2007.
  17. M. Onsjoe and O. Watanabe, Finding most likely solutkons, Proc. Computation and Logic in the Real World - Third Conference of Computability in Europe (CiE 2007), LNCS 4497:758--767, 2007.
  18. M. Onsjoe and O. Watanabe, A simple message passing algorithm for graph partition problem, Proc. 17th International Symposium on Algorithms and Computation (ISAAC'06), LNCS 4288:507-516, 2006.
  19. O. Watanabe and M. Yamamoto, Average-case analysis for the MAX-2SAT problem, Proc. 9th International Conference on Theory and Application of Satisfiability Testing (SAT'06), LNCS 4142: 277--282, 2006.
  20. O. Watanabe, Some heuristic analysis of local search algorithms for SAT problems, Proc. 3rd International Symposium on Stochastic Algorithms, LNCS 3777:14--25, 2005.
  21. J.Y. Cai and O. Watanabe, Random access to advice strings and collapsing results, Proc. 15th International Symposium on Algorithms and Computation (ISAAC'04), LNCS 3341:209--220, 2004.
  22. K. Hatano and O. Watanabe, Learning r-of-k functions by boosting, Proc. 15th International Conference on Algorithmic Learning Theory (ALT 2004), LNCS 3244:114--126, 2004.
  23. O. Watanabe, T. Sawai, and H. Takayashi, Analysis of a randomized local search algorithm for LDPCC decoding problem, Proc. 2nd International Symposium on Stochastic Algorithms, LNCS 2827: 50--60, 2003.
  24. J.Y. Cai and O. Watanabe, On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results, Proc. 9th International Computing and Combinatorics Conference (COCOON'03), LNCS 2697: 202--211, 2003.
  25. J.Y. Cai and O. Watanabe, Relativized collapsing results under stringent oracle access, FIT Letters, 1(1): 1--2, 2002.
  26. S. Aida, M. Crasmaru, K. Regan, and O. Watanabe, Games with a uniqueness property, Proc. 19th Symposium on Theoretical Aspects of Computer Science, LNCS 2285: 396--407, 2002.
  27. T. Hofmeister, U. Schoning, R. Schuler, and O. Watanabe, A Probabilistic 3-SAT Algorithm Further Improved, Proc. 19th Symposium on Theoretical Aspects of Computer Science (STACS'02), LNCS 2285: 193--202, 2002.
  28. R. Gavalda and O. Watanabe, Sequential sampling algorithms: Unified analysis and lower bounds, Proc. 1st International Symposium on Stochastic Algorithms, LNCS 2264: 173--187, 2001.
  29. J. Balcazar, Y.Dai, O. Watanabe, Provably fast trainning algorithms for support vector machines, Proc. 1st IEEE International Conference on Data Mining, IEEE: 43--50, 2001.
  30. J. Balcazar, Y.Dai, O. Watanabe, A Randam Sampling Technique for Training Support Vector Machines(For Primal-form Maximal-Margin Classifiers), Proc. 12th International Conference on Algorithmic Learning Theory (ALT 2001), LNAI 2225: 119--134, 2001.
  31. K. Okamoto and O. Watanabe, Deterministic application of Grover's quantum search algorithm, Proc. 7th Annual International Conference on Computing and Combinatorics (COCOON'01), LNCS 493--501, 2001.
  32. S. Aida, R. Schuler, T. Tsukiji, and O. Watanabe, On the difference between polonomial-time many-one and truth-table reducibilities on distributional problems, Proc. 18th International Symposium on Theoretical Aspects of Computer Science (STACS'01), LNCS 2010: 52--62, 2001.
  33. K. Amano, J. Tromp and O. Watanabe , On a generalized ruin problem, Proc. 4th Int'l Workshop on Algorithms for Combinatorial Optimization Problems,APPROX'01, and 5th Int'l Workshop on Randomized and Approximation Techniques in Computer Science, RANDOM'01, LNCS 2129:181--191, 2001.
  34. C. Domingo and O. Watanabe, MadaBoost: A modification of AdaBoost, Proc. of 3th Annual Confernce on Computational Learning Theory (COLT'00) , ACM: 180--189, 2000. Also see C-133.
  35. C. Domingo and O. Watanabe, Scaling up a boosting-based learner via adaptive sampling , Proc. of Knowledge Discovery and Data Mining ( PAKDD'00), LNAI 1805: 317--328, 2000.
  36. C. Domingo, R. Gavalda, and O. Watanabe, Adaptive sampling methods for scaling up knowledge discovery algorithms, Proc. 2nd International Confernce on Discovery Science (DS'99), LNAI 1721: 172--183, 1999.
  37. P.B. Miltersen, N.V. Vinodchandran, and O. Watanabe, Super-polynomial verseus half-exponential circuit size exponential hierarchy, Proc. 5th Annual International Computing and Combinatorics Confernce (COCOON'99), LNCS 1627: 210--220, 1999.
  38. C. Domingo, R. Gavalda, and O. Watanabe, Practical algorithms for on-line sampling, Proc. 1st International Coference on Discovery Science (DS'98), LNAI 1532: 150--162, 1998.
  39. C. Domingo, O. Watanabe, and T. Yamazaki, A role of constaint in self-organization, Proc. 2nd Internatiional Workshop (RANDOM'98), LNCS 1518: 307--318, 1998. Also see C-124.
  40. W. Lindner, and R. Schuler, and O. Watanabe, Resource bounded measure and learnability, Proc. 13th IEEE conference on Computational Complexity , IEEE: 261--270, 1998.
  41. S. Horie and O. Watanabe, Hard instance generataion for SAT, Proc. 8th International Symposium on Algorithms and Computation (ISAAC'97), LNCS 1350: 22--31, 1997.
  42. C. Domingo, T. Tsukiji, and O. Watanabe, Partial Occam's razor and its appliations, Proc. 8th International Workshop on Algorithm Learning Thoery (ALT'97), LNAI 1316: 85--99, 1997.
  43. O. Watanabe and O. Yamashita, An improvement of the digital cash protocol of Okamoto and Ohta, Proc. 7th International Symposium on Algorithms and Computation (ISAAC'96), LNCS 1187: 436--445, 1996.
  44. H. C. Lau and O. Watanabe, Randomized approximation of the constraint satisfaction problem, Proc. 5th Scandinavian Workshop on Algorithm Theory, LNCS 1097: 76--87, 1996.
  45. L. Hemachandra, Z. Jiang, J. Rothe, and O. Watanabe, The join can lower complexity , Proc. 2nd Annual Internantional Computing and Combinatorics Conference (COCOON'96), LNCS 1090: 260--267, 1996.
  46. J. Kobler and O. Watanabe, New collapse consequence of NP having small circuits, Proc 22nd International Collquim on Automata Languages and Programming (ICALP'95), LNCS 944: 196--207, 1995.
  47. R. Schuler and O. Watanabe, Towards average-case complexity analysis of NP optimization problems, Proc. 10th Structure in Compleexity Theory Conference, IEEE: 148--159, 1995.
  48. R. Book and O. Watanabe , On random hard sets for NP, Proc. 5th International Symposium on Algorithms and Computation (ISAAC'94), LNCS 834: 47--55, 1994.
  49. O. Watanabe, Test instance generation for promised NP seaarch problems, Proc. 9th Structure in Complexity Theory Conference, IEEE: 205--216, 1994.
  50. J. Balcazar, J. Diaz, R. Gavalda, and O. Watanabe, An optimal parallel algorithm for learning DFA, Proc. 7th ACM Cnference on Computational Learning Theory (COLT'94), ACM: 208--217, 1994.
  51. T. Tierauf, S. Toda, and O. Watanabe, On sets bounded truth-table reducible to P-selective sets, Proc. 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) , LNCS 775: 427--438, 1994.
  52. M. Ogiwara, T. Tierauf, S. Toda, and O. Watanabe, On closure properties of #P in the context of Pfo # P, Proc. 8th Structure in Complexity Theory Conference, IEEE: 139--146, 1993.
  53. K. kurosawa and O. Watanabe, Computational and statistical indistinguishability, Proc. 3rd Internantional Symposium on Algorithms and Computation (ISAAC'92), LNCS 650: 430--438, 1992.
  54. L. Longpre and O. Watanabe, On symmetry of information and polynomial time invertibility, Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92), LNCS 650: 410--419, 1992.
  55. J. Balcazar, J. Diaz, R. Gavalda, and O. Watanabe, A note on the query complexity of learning DFA, Proc. 3rd Workshop on Algorithmic Learning Theory (ALT'92), Japanese Society for Artificial Intelligence: 53--62, 1992.
  56. O. Watanabe, On the complexity of small description and related topics, Proc. 17th Mathmatical Foundations of Computer Science (MFCS'92), LNCS 629: 82--94, 1992.
  57. L. Hemachandra, M. Ogiwara, and O. Watanabe, How hard are sparse sets?, Proc. 7th Structure in Conplexity Theory Conference, IEEE: 222--238, 1992.
  58. R. Gavalda and O. Watanabe, On the computational complexity of small descriptions, Proc. 6th Structure in Complexity Theory Conference, IEEE: 89--101, 1991.
  59. E. Allender, L. Hemachandra, M. Ogiwata, O. Watanaabe, Relating equivalence and reducibility to sparse sets, Proc. 6th Structure in Complexity Theory Conference, IEEE: 220--229, 1991.
  60. R. Gavalda, L. Torenvilet, J. Balcazar, and O. Watanabe, Generalized Kolmogorov complexity in relativized separations, Proc. Mathematical Foundations of Computer Science (MFCS'90), LNCS 452: 269--276, 1990.
  61. O. Watanabe, Structural analyses on the complexity of inverting functions, Proc. International Symposium (SIGAL'90), LNCS 450: 31--38, 1990.
  62. O. Watanabe, A formal study of learning via queries, Proc. 15th International Colloquim on Automata, Languages and Progamming (ICALP'90), LNCS 443: 139--152, 1990.
  63. M. Ogiwara and O. Watanabe, On polynomial time bounded truth-table reducibility of NP sets to sparse sets, Proc. 22nd Annual ACM symposium on Theory of Computing (STOC'90), ACM: 457--467, 1990.
  64. S. Tang and O. Watanabe, On polynomial-time turning and many-one completeness in PSPACE, Proc. 4th Structure in Complexity Theory Conference, IEEE: 15--23, 1989.
  65. O. Watanabe, On 1-tt-sparseness of nondeterministic complexity classes, Proc. 15th International Colloquim on Automata, Languages and Progamming (ICALP'90), LNCS 226: 697--709, 1988.
  66. A. Allender and O. Watnabe, Kolmogorov complexity and degrees of tally sets , Proc. 3rd Structure in Complexity Theory Conference, IEEE: 102--112, 1988.
  67. S. Tang and O. Watanabe, On tally relativizations of BP-complexity classes,, Proc. 3rd Structure in Complexity Theory Conference, IEEE: 10--18 , 1988.
  68. O. Watanabe, Polynomial time reducibility to a set of small density, Proc. 2nd Structure in Complexity Theory Conference, IEEE: 138--146 , 1987.
  69. R. Book, P. Orponen, D. Russo, and O. Watanabe , On exponential lowness, Proc. 13th International Colloquium on Automata, Languages and Programming (ICALP'86), LNCS 226: 40--49, 1986.
  70. K. Ko, U. Schoning, P. Orponen, and O. Watanabe , What is a hard instance of a computational problem?, Proc. 1st Structure in Complexity Theory Conference, LNCS 223: 197--217, 1986.

Invited Lectures/Papers

  1. S. Tamaki and O. Watanabe, Local restrictions from the Furst-Saxe-Sipser paper, Theory of Computing Systems, 60(1): 20-32, 2017. 10.1007/s00224-016-9730-0
  2. T. Imai and O. Watanabe, Relating sublinear space computability, in Proc. of the 42nd Int'l Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'16), LNCS 9587: 17-28, 2016. 10.1007/978-3-662-49192-8_2
  3. O. Watanabe, Sublinear space complexity, in Workshop on Connection between Algorithm Design and Complexity Theory, Simons Institute, 2015.
  4. 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 8808: 394-405, 2014. 10.1007/978-3-319-13350-8_29
  5. O. Watanabe, SETH, The Strong Exponential Time Hypothesis and the structure of the solution space of CNF-SAT problems, Collective Dynamics in Information Systems, KITPC/ITP-CAS, Chinese Academy of Science, Beijing, 2014.10.
  6. O. Watanabe, Perturbed k-linear-equation problems, Workshop at IIT Kanpur, Kanpur, 2012.8.
  7. J. Cai and O. Watanabe, Stringent relativization: a new approach for studying complexity classes, SIGACT News, Vol.37, Dec. Issue (#140), 2006.
  8. O. Watanabe, Computational Complexity and Its Applications, Theory and Applications of Models of Computation (TAMC05), Kunming, 2005.
  9. J. Cai and O. Watanabe, Stringent relativization, Proc. 23rd Conference on Foundations of Software Technology and Theoretical Computer Science, LNCS 2914: 408--419, 2003.
  10. 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.
  11. O. Watanabe, Algorithmic aspects of boosting, Progress in Discovery Science, LNAI 2281:349--359, 2002.
  12. O. Watanabe, How can computer science contribute to knowledge discovery?, SOFSEM 2001Theory and Practice of Informatics, 136--151, 2001.
  13. O. Watanabe, Sequential sampling techniques for algorithmic learning theory, Proc. 11th International Conference on Algorithmic Learning Theory (ALT'00), LNAI 1968: 27--40, 2000.
  14. O. Watanabe, Simple sampling technique for discovery science, IEICE Trans. Information and Systems, E83-D(1): 19--26, 2000.
  15. O. Watanabe, From learning theory to discovery science, Proc. 26th International Colloquim on Automata, Languages and Programming (ICALP'99), LNCS 1664: 134--148, 1999.
  16. Japanese record, omitted.
  17. O. Watanabe, A view of structural complesity theory, Curent Trends in Theoretical Computer Science, World Scientific, 451-468, 1993.
  18. Japanese record, omitted.
  19. Japanese record, omitted.
  20. R. Book, and O. Watanabe, A view of structural complexity theory, The Bulletin of the European Association of Theoretical Computer Science, 39: 122--138, 1993.
  21. O. Watanabe, On one-way functions, Combinatorics, Computing and Complexity, 98--131, 1989.
  22. O. Watanabe, On the computational complexity of small descriptions, 17th Int'l Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS 629: 82--94, 1987.
  23. Japanese record, omitted.

Books

  1. O. Watanabe, Randomness in Algorithms (Chap.24 of Randomness through Computation (H. Zenil ed.)), World Scientific, Chap 24, 297--308, 2011.
  2. T. Asano, Nakano, Y. Okamoto, and O. Watanabe, Algorithm and Computation, Proc. 22nd International Symposium on Algorithms and Computation (ISAAC'11), Springer-Verlag, Lecture Notes in Computer Science 7074, 2011.
  3. O. Watanabe and T. Zeugmann, Proc. 5th International Symposium on Stochastic Algorithms: Foundations and Applications (SAGA'10), Springer-Verlag, Lecture Notes in Computer Science 5792, 2010.
  4. A. Sharma and O Watanabe (eds.), Algorithmic Learning Theory, Theoretical Computer Scinece, Elsevier, 288(2), 2002.
  5. A. Sharma and O Watanabe (eds.), Special Issue on Algorithmic Learning Theory, Theoretical Computer Scinece, Elsevier, 305(1), 2001.
  6. O. Watanabe and T. Yokomori (eds.), Proc. 10th International Conference on Algorithmic Learning Theory, Springer-Verlag, Lecture Notes in Artificial Intelligence 1720, 1999.
  7. O. Watanabe (ed.), Kolmogorov Complexity: Theory and Relations to Computational Complexity, Springer-Verlag, EATCS Monographs on Theoretical Computer Science, 1992.
  8. T. Ibaraki and O. Watanabe (eds.), Special Section on Theoretical Foundation of Computing , IEICE, Vol. E75-D (1), 1992.
  9. O. Watanabe, On the Structure of Intractable Complexity Classes , Dr. Eng. Thesis (Tokyo Institute of Technology), , 1987.
watanabe (at) c.titech.ac.jp