Osamu WATANABE

Mail: watanabe-at-is.titech.ac.jp
Click here for Watanabe's home page (Japanese).

New Topics (2007.10.25 update)

• Doctoral Students and Post Doc.s Invited!
  Global COE CompView invites students to its doctoral program and researchers to six post doc. positions.
  • As one project of the Global COE (Center of Excellence) program, our "Computationisms as Foundations of Sciences" (CompView) has been accepted, and the project got started from August 2007.
  • We propose a education/research program for establishing a new paradigm of science based on "computation" implemented on high performance computing such as supercomputers.
  • The establishment of excellent doctoral education is expected for the GCOE program, we are planning to create a doctoral education program supported by the GCOE members, special faculty staffs, and post doc.s.

  Please visit our home page: http://compview.titech.ac.jp (English page).

• We succeeded giving an index to each of all SUDOKU solutions, approximately 6.7*10**21. Vist our SUDOKU index page for computing the index of your SUDOKU solution!
• For Summer School for Chinese Young Researchers (JiaoTong Univ., Shanghai, 2002) I made up lecture notes on computational complexity theory. (Some minor revision has been made on May 2005).
  1. Part I: Basics (part1 pdf file)
  2. Part II: Some Advanced Topics (part2 pdf file)
  The materials there can be taught in a week.

Research Interest

With a pointer to some representative paper of mine, and some related web pages.

• Computational Complexity Theory:
  • P versus NP problem (worst case):
    - J. Cai and O.Watanabe, On proving circuit lower bounds against the polynomial-time hierarchy, SIAM Journal on Computing, 33(4): 984--1009, 2004.
    - J. Cai and O.Watanabe, Random access to advice strings and collapsing result, Algorithmica, 45(1): 43--57, 2006.
  • P versus NP problem (average case):
    == Average-Case Complexity Forum (by Jie Wang).
  • Design and analysis of randomized algorithms:
    - M.Onsjoe and O.Watanabe, A simple message passing algorithm for graph partition problem, ISAAC'06, LNCS 4288:507-516, 2006.
    - O.Watanabe and M.Onsjoe, Finding most likely solutions, CiE'07, LNCS:, 2007.
• Applications of Theory of Computation:
  • Computational Learning and Discovery Science:
    - C. Domingo and O. Watanabe, MadaBoost: A modification of AdaBoost, COLT'00, Proc. 180--189, 2000.
    - 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.
    == Algorithmic Learning Theory (ALT) Workshop Archives.
    == Discovery Science home page.
  • Computational Analysis of Brain

Survey Papers and/or Web Pages on Some of My Research Topics

• Publication List (with links to papers)
• Random Sampling for Knowledge Discovery (pdf file, for SOFSEM, 2001)
• Algorithmic Aspect of Boosting (pdf file, for DS Book from Springer, 2001)
• Random Sampling for Computer Scinece (pdf file, for IEICE Trans., 2000)
• Lecture Note: Introduction to Computational Complexity Theory (see above)
• Public Software and Data: SAT Test Instance Generation Page (1998)
• What is Structural Complexity Theory (pdf file, for the EATCS Bulletin, 1990; with R. Book)

Professional Activities

• Editor of Theoretical Computer Science (TCS)
• Editor of Theory of Computing Systems (TOCS) (former name: Mathematical Systems Theory (MST))
• Vice Chair of the Japan Chapter of EATCS, the European Association for Theoretical Computer Science.

More Information

• TiTech Dept. Math & Comput. Technical Reports (You can find some of my recent works (from 1998) here)
• TiTech Dept. Comp. Sci. Technical Reports (You can find some of my old works (before 1997) here)

Links

• Complexity Seminar Home Page (in Japanese)
• ResearchIndex (a free search engine for scientific info.)
• Scirus (a free search engine for scientific info.)

Address

Postal Address:
Department of Mathematical and Computing Science
Tokyo Institute of Technology
Meguro-ku Ookayama, Tokyo 152-8552
Japan
email address: watanabe-at-is.titech.ac.jp
fax: +81-3-5734-3210, tel: +81-3-5734-2688