Publication List

Osamu Watanabe (Last Update 11.26.2007.)

Journal Papers

  1. T. Hofmeister, U. Schoening, R. Schuler, and O. Watanabe, Randomized algorithms for 3-SAT, Theory of Comput. Systems, 40: 249--262, 2007.
  2. J.Y. Cai and O. Watanabe, Random access to advice strings and collapsing result, Algorithmica, 45(1): 43--57, 2006.
  3. S. Balaji, H.M. Mahmoud, and O. Watanabe, Distributions in the Ehrenfest process, Statistics and Probability Letters, 76(7): 666-674, 2006. Available as a Res. Report C-210 (abstract, gzipped ps file).
  4. O.Watanabe, Sequential sampling techniques for algorithmic learning theory, Theoretical Computer Science, 348(1,2): 3--14, 2005.
  5. O.Watanabe, Pseudo expectation: A tool for analyzing local search algorithms, Progress of Theoretical Physics, Supplement, (157): 338--344, 2005. Available as a Res. Report C-195 (abstract, gzipped ps file).
  6. R. Kato and O. Watanabe, Substring search and repeat search using factor oracles, Information Processing Letters, 93(6): 269-274, 2005.
  7. J. Cai and O. Watanabe, On proving circuit lower bounds against the polynomial-time hierarchy, SIAM Journal on Computing, 33(4): 984--1009, 2004. Available as a Res. Report C-167 (abstract, gzipped ps file).
  8. J. Cai and O. Watanabe, Relativized collapsing between BPP and PH under stringent oracle access, Information Processing Letters, 90: 147--154, 2004. Available as a Res. Report C-168 (abstract, gzipped ps file).
  9. S. Aida, M. Crasmaru, K. Regan, and O. Watanabe, Games with a uniqueness property, Theory of Comput. Systems, 37: 29--47, 2003. Available as a Res. Report C-155 (abstract, gzipped ps file).
  10. 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.
  11. 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. Available as a Res. Report C-131 (abstract, gzipped ps file).
  12. W. Lindner, R. Schuler, and O. Watanabe, Resource-bounded measure and learnability, Theory of Comput. Systems, 33: 151--170, 2000.
  13. J. Kobler and O.Watanabe, New collapse consequence of NP having small circuits, SIAM Journal on Computing, 28(1): 311--324, 1998.
  14. 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.
  15. Japanese record, omitted.
  16. C. Domingo, T. Tsukiji, and O. Watanabe, Partial Occam's razor its applications, Information Processing Letters, 64: 179--185, 1997. Available from CS. Tech. Report Archive.
  17. L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe, Pollynomial-time multi-selectivity, J. of Universal Computer Science, 3(3): 197--229, 1997.
  18. H .C. Lau and O. Watanabe, Randomized approximation of the constraint satisfation problem, Nodric Journal of Computing, 3: 405--424, 1996.
  19. J. Balcazar, J. Diaz, R. Gavalda, and O. Watanabe, An optimal parallel algorithm for learning DFA, Journal of Universal Computer Science, , 1996. Available from CS. Tech. Report Archive.
  20. R .Book and O. Watanabe, On random hard sets for NP, Information and Computation, 125: 70--76, 1996.
  21. 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.
  22. 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.
  23. L. Longpre and O. Watanabe, On symmetry of information and polynomial time invertibility, Information and Computation, 121(1): 14--22, 1995.
  24. R. Rao, J. Rothe, and O. Watanabe, Upward separation for FewP and related classes, Information Processing Letters, 52(4): 175--180, 1994.
  25. T. Thierauf, S. Toda, and O. Watanabe, On closure properties of GapP, Computational Complexity, 4: 242--261, 1994.
  26. J. Balcazar, J. Diaz, R. Gavalda, and O. Watanabe, The query complexity of learning DFA, New Generation Computing, 12: 337--358, 1994.
  27. R. Gavalda and O. Watanabe, Structural analysis of polynomial time query learnability, Mathematical Systems Theory, 27: 231--256, 1994.
  28. O. Watanabe, A framework for polynomial time query learnability, Mathematical Systems Theory, 27: 211--229, 1994.
  29. P. Orponen, K. Ko, U. Schoning, and O. Watanabe, Instance Commplexity, Journal of the Association for Computing Machinery, 41(1): 96--121, 1994.
  30. R. Gavalda and O. Watanabe, On the computational complexity of small descriptions, SIAM Journal on Computing, 22(6): 1257--1275, 1993.
  31. S. Toda and O. Watanabe, Some structural analysis on the complexity of inverse functions, Mathematical Systems Theory, 26: 203--214, 1993.
  32. N. Abe and O. Watanabe, polonomially sparse variations and reducibility among prediction problems, IEICE Trans. Information and Systems, E75-D(4): 449--458, 1992.
  33. 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.
  34. S. Toda and O. Watanabe, Polynomial time 1-turing reductions from #PH to #P, Theoretical Computer Science, 100(1): 205--221, 1992.
  35. S. Tang and O. Watanabe, On polynomial -time turing and many-one completeness in PSPACE, Theoretical Computer Science, 97(2): 199--215, 1992.
  36. O. Watanabe, On polynomial-time one-truth-table reduccibility to sparse sets, Journal of Computer and System Science, 44(3): 500--516, 1992.
  37. O. Watanabe, On intractability of the class UP, Mathematical Systems Theory, 24: 1--10, 1991.
  38. O. Watanabe, A note on the p-isomorphism conjecture, Theoretical Computer Science, 83: 337--343, 1991.
  39. 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.
  40. A. Allender and O. Watanabe, Kolmogorov complexity and degrees of tally sets , Information and Computation, 86: 160--178, 1990.
  41. S.Tang and O.Watanabe, On tally relativizations of BP-commplexity classes, SIAM Journal on Computing, 18: 449--462, 1989.
  42. 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.
  43. O. Watanabe, On hardness of one-way functions, Information Processing Letters, 27: 151--157, 1988.
  44. O. Watanabe, A Comparison of polynomial time completeness notions, Theoretical Computer Science, 54: 249--265, 1987.
  45. Japanese record, omitted.
  46. O. Watanabe, On one-one polynomial trade off problem on on-line probabilistic turing machines, Theoretical Computer Science, 38: 157--165, 1985.
  47. O. Watanabe, The time-precision trade off problem on on-line probabilistic turing machines, Theoretical Computer Science, 24: 105--117, 1983.
  48. O. Watanabe, A fast algorithm for finding all shortest paths, Information Processing Letters, 13: 1--3, 1981.
  49. O. Watanabe, Another application of recursion introduction, Information Processing Letters, 10: 116--119, 1980.

Conference Papers (Refereed)

  1. 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.
  2. 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:, 2007.
  3. 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.
  4. 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. Available as a Res. Report C-225 (abstract, gzipped ps file).
  5. O. Watanabe, Some heuristic analysis of local search algorithms for SAT problems, Proc. 3rd International Symposium on Stochastic Algorithms, LNCS 3777:14--25, 2005. Available as a Res. Report C-198 (abstract, gzipped ps file).
  6. 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. Available as a Res. Report C-199 (abstract, gzipped ps file).
  7. 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. Available as a Res. Report C-194 (abstract, gzipped ps file).
  8. 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. Available as a Res. Report C-173 (abstract, gzipped ps file).
  9. 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. Available as a Res. Report C-167 (abstract, gzipped ps file).
  10. J.Y. Cai and O. Watanabe, Relativized collapsing results under stringent oracle access, FIT 1(1): 1--2, 2002. Available as a Res. Report C-168 (abstract, gzipped ps file).
  11. 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. Available as a Res. Report C-155 (abstract, gzipped ps file).
  12. 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. Available as a Res. Report C-146 (abstract, gzipped ps file).
  13. 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. Available as a Res. Report C-156 (abstract, gzipped ps file).
  14. 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. Available as a Res. Report C-155 (abstract, gzipped ps file).
  15. 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. Available as a Res. Report C-149 (abstract, gzipped ps file).
  16. 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. Available as a Res. Report C-148 (abstract, gzipped ps file).
  17. 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. Available as a Res. Report C-143 (abstract, gzipped ps file).
  18. 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.
  19. 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. Available as a Res. Report C-138 (abstract, gzipped ps file). Also see C-133.
  20. 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. Available as a Res. Report C-139 (abstract, gzipped ps file).
  21. 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. Available as a Res. Report C-131 (abstract, gzipped ps file).
  22. 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. Available as a Res. Report C-130 (abstract, gzipped ps file).
  23. 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. Available as a Res. Report C-123 (abstract, gzipped ps file).
  24. 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. Available as a Res. Report C-127 (abstract, gzipped ps file). Also see C-124.
  25. W. Lindner, and R. Schuler, and O. Watanabe, Resource bounded measure and learnability, Proc. 13th IEEE conference on Computational Complexity , IEEE: 261--270, 1998.
  26. 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. Available from CS. Tech. Report Archive.
  27. 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. Available from CS. Tech. Report Archive.
  28. 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. Available from CS. Tech. Report Archive.
  29. 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.
  30. 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.
  31. 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.
  32. 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.
  33. 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.
  34. O. Watanabe, Test instance gereration for promised NP seaarch problems, Proc. 9th Structure in Complexity Theory Conference, IEEE: 205--216, 1994.
  35. 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.
  36. 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.
  37. 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.
  38. K. Kurosawa and O. Watanabe, Computational and statistical indistinguishability, Proc. 3rd Internantional Symposium on Algorithms and Computation (ISAAC'92), LNCS 650: 430--438, 1992.
  39. 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.
  40. 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.
  41. 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.
  42. L. Hemachandra, M. Ogiwara, and O. Watanabe, How hard are sparse sets?, Proc. 7th Structure in Conplexity Theory Conference, IEEE: 222--238, 1992.
  43. R. Gavalda and O. Watanabe, On the computational complexity of small descriptions, Proc. 6th Structure in Complexity Theory Conference, IEEE: 89--101, 1991.
  44. 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.
  45. 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.
  46. O. Watanabe, Structural analyses on the complexity of inverting functions, Proc. International Symposium (SIGAL'90), LNCS 450: 31--38, 1990.
  47. 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.
  48. 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.
  49. 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.
  50. 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.
  51. A. Allender and O. Watnabe, Kolmogorov complexity and degrees of tally sets , Proc. 3rd Structure in Complexity Theory Conference, IEEE: 102--112, 1988.
  52. S. Tang and O. Watanabe, On tally relativizations of BP-complexity classes,, Proc. 3rd Structure in Complexity Theory Conference, IEEE: 10--18 , 1988.
  53. O. Watanabe, Polynomial time reducibility to a set of small density, Proc. 2nd Structure in Complexity Theory Conference, IEEE: 138--146 , 1987.
  54. 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.
  55. 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. Japanese record, omitted.
  2. J. Cai and O. Watanabe, Stringent relativization: a new approach for studying complexity classes, SIGACT News, Vol.37, Dec. Issue (#140), 2006.
  3. O. Watanabe, Computational Complexity and Its Applications, Theory and Applications of Models of Computation (TAMC05), Kunming, 2005.
  4. J. Cai and O. Watanabe, Stringent relativization, Proc. 23rd Conference on Foundations of Software Technology and Theoretical Computer Science, LNCS 2914: 408--419, 2003. Available as a Res. Report C-199 (abstract, gzipped ps file).
  5. 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.
  6. Japanese record, omitted.
  7. Japanese record, omitted.
  8. O. Watanabe, On boosting and its implementation techniques (in Japanese), The Brain and Neural Networks, 9(3): 196--203, 2002.
  9. O. Watanabe, Algorithmic aspects of boosting, Progress in Discovery Science, LNAI 2281:349--359, 2002. Available as a Res. Report C-163 (abstract, gzipped ps file).
  10. O. Watanabe, How can computer science contribute to knowledge discovery?, SOFSEM 2001Theory and Practice of Informatics, 136--151, 2001. Available as a Res. Report C-162 (abstract, gzipped ps file).
  11. O. Watanabe, Sequential sampling techniques for algorithmic learning theory, Proc. 11th International Conference on Algorithmic Learning Theory (ALT'00), LNAI 1968: 27--40, 2000.
  12. O. Watanabe, Simple sampling technique for discovery science, IEICE Trans. Information and Systems, E83-D(1): 19--26, 2000. Available as a Res. Report C-137 (abstract, gzipped ps file).
  13. O. Watanabe, From learning theory to discovery science, Proc. 26th International Colloquim on Automata, Languages and Programming (ICALP'99), LNCS 1664: 134--148, 1999. Available as a Res. Report C-132 (abstract, gzipped ps file).
  14. Japanese record, omitted.
  15. O. Watanabe, A view of structural complesity theory, Curent Trends in Theoretical Computer Science, World Scientific, 451-468, 1993.
  16. Japanese record, omitted.
  17. Japanese record, omitted.
  18. 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.
  19. O. Watanabe, On one-way functions, Combinatorics, Computing and Complexity, 98--131, 1989.
  20. 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.
  21. Japanese record, omitted.

Books

  1. Japanese record, omitted.
  2. Japanese record, omitted.
  3. A. Sharma and O Watanabe (eds.), Algorithmic Learning Theory, Theoretical Computer Scinece, Elsevier, 288(2), 2002.
  4. A. Sharma and O Watanabe (eds.), Special Issue on Algorithmic Learning Theory, Theoretical Computer Scinece, Elsevier, 305(1), 2001.
  5. Japanese record, omitted.
  6. Japanese record, omitted.
  7. O. Watanabe and T. Yokomori (eds.), Proc. 10th International Conference on Algorithmic Learning Theory, Springer-Verlag, Lecture Notes in Artificial Intelligence 1720, 1999.
  8. Japanese record, omitted.
  9. Japanese record, omitted.
  10. Japanese record, omitted.
  11. Japanese record, omitted.
  12. O. Watanabe (ed.), Kolmogorov Complexity: Theory and Relations to Computational Complexity, Springer-Verlag, EATCS Monographs on Theoretical Computer Science, 1992.
  13. T. Ibaraki and O. Watanabe (eds.), Special Section on Theoretical Foundation of Computing , IEICE, Vol. E75-D (1), 1992.
  14. O. Watanabe, On the Structure of Intractable Complexity Classes , Dr. Eng. Thesis (Tokyo Institute of Technology), , 1987.

Public Softwares

  1. T. Motoki and O. Watanabe, Test instance generators for SAT, Public Softwares and Data, , 1997.
watanabe@is.titech.ac.jp