For Prospective Students

The main focus of this laboratory is on "algorithms" and "discrete mathematics". Current algorithmic innovations in information retrieval technology such as “Google's PageRank” and security technology such as “Apple's Local Differential Privacy” are leading to business creation on a national scale. However, it is important to note that both PageRank and local Differential Privacy are algorithms, developed out of basic and theoretical researches within algorithm and discrete mathematics, and were not application-oriented for business use from the beginning. In this laboratory, too, we do not conduct research with applications in mind from the start. Rather, we pursue thorough theoretical research with an emphasis on basic and theoretical research.

Type of persons we are seeking and our goals

This laboratory aims to strengthen its research in the following areas, with a focus on algorithms and discrete mathematics:

  • 1. Exploration of deep theories;
  • 2. Algorithm development utilizing theoretical knowledge with respect to real-world data; and
  • 3. Generation of cutting-edge knowledge in numerous application areas such as machine learning, deep learning, data mining, etc. using knowledge of discrete mathematics and algorithms.

Through item 1, we aim to produce people with "creativity" who will set forth results and theories that will leave their mark on history.
A person who makes full use of items 2 and 3 will be able to conduct cutting-edge research in a wide range of fields at any given time, including machine learning of today, data mining in the past, and bioinformatics. Our goal is not to produce personnel who specialize only in one specific research field, but someone who will perform world-class work in a wide range of fields over an extended period such as 20 and 30 years.

Specific Research

The main focus of this laboratory is on "algorithms" and "discrete mathematics" as well as their applications. In particular, we plan to conduct the following research on "graphs":

  • 1. Development of theoretically fast and accurate algorithms for problems dealing with graphs, or prove NP-hardness, etc.;
  • 2. Development of implementable algorithms for graphs that appear in the real world, using theoretical tools such as discrete mathematics;
  • 3. Development of algorithms that are theoretically or practically fast in the case of restricted families of graphs, such as planar graphs or social networks;
  • 4. Application of knowledge and implementation of graph algorithms to machine learning, especially online learning and deep learning;
  • 5. Research on graphs as they appear in natural language processing, machine learning, databases, data mining, programming language fields, etc.; and
  • 6. Combinatorial optimization and discrete mathematics.

For "theoretical" research, we plan to provide highly motivated students opportunities to interact with top theoretical researchers overseas. For other research, we plan to work with domestic and international collaborators, including companies.

Facilities and Financial Support

Please consult with us as necessary materials will be provided. We provide a display that is 25 inches or larger and 4K or other types and a laptop computer such as Windows or MacBook Pro of your choice at the time of assignment.
We provide financial support to master's and doctoral students as research assistants (RAs) so that they can concentrate on their research activities with as little financial worry as possible. Master's students are guaranteed to receive at least 100,000-120,000 yen per month.
For doctoral students, a monthly stipend of 180,000-200,000 yen is available through an external research grant. Please contact us for details. When combined with the Japan Society for the Promotion of Science Postdoctoral Fellowship DC1/DC2 (200,000 yen/month), the total amount that a researcher can receive will be nearly 300,000 yen.
For more information about the entrance examination, please visit the page of Department of Computer Science, Graduate School of Information Science and Technology, the University of Tokyo.

For more information about Dr. Kawarabayashi, please visit this weblink

Dr. Kawarabayashi is also a professor at the National Institute of Informatics (NII).
Please visit this weblink for information about the NII.

Lab introduction slides