Osamu WATANABE

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

Some Topics

• I am running CompView Global COE project under the Global COE (Center of Excellence) program of Japanese government.
  • We propose a research program for establishing a new paradigm or framework of science that seeks to rethink various scientific phenomena from the point of view of computation, which we call the CompView approach.
  • We also made up a doctoral program for creating specialits of the CompView approach; those who can pursue this new paradigm. Our program is to foster doctoral students to have skills in both high-performance computing and mathematical modeling/analysis.
  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): for example,
    - J. Cai and O.Watanabe, Random access to advice strings and collapsing result, Algorithmica 45(1): 43--57, 2006.
    - M. Agrawal and O. Watanabe, One-way functions and the Berman-Hartmanis conjecture, CCC'09, 194--202, 2009. (Tech. report version: C-260)
  • Design and analysis of randomized algorithms: for example,
    - M. Onsjoe and O. Watanabe, Finding most likely solutions, Theory of Computing Systems 45(4): 926--942, 2009.
    - A. Coja-Oghlan, M. Onsjoe, and O. Watanabe, Propagation connectivity of random hypergraphs, RANDOM'10, 2010, to appear. (Tech. report version: C-271)
• Applications of Theory of Computation:
  • Computational Learning and Discovery Science:
    - C. Domingo and O. Watanabe, MadaBoost: A modification of AdaBoost, COLT'00, 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.

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)

Professional Activities

• Editor of Theoretical Computer Science (TCS)
• Editor of Theory of Computing Systems (TOCS) (former name: Mathematical Systems Theory (MST))
• 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

underconstruction

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