About

Algorithms based on mathematical theory have created progress for human civilization. At present, algorithmic innovations, information searches, and genome information processing are connected to the creation of large business on a national scale. In the 21st century, it is expected that developments in advanced computer science will solve mankind’s various problems, but many of these are difficult problems which cannot be solved even if a supercomputer is used. In order to solve these problems, new innovations in algorithms are needed, and new algorithmic technologies which are based on mathematical science have top-priority significance. In particular, the high-speed implementation for large networks and data on the scale of billions of units shall be raised, and will be applied to a wide range of fields, such as transportation, Web analysis and biotechnology. Theoretical research in this proposal could be a breakthrough for solving these global problems.

We plan to work on the following three projects.

1. Submodular function appears everywhere in optimization problems and machine learning problems. In this proposal, we attempt to consider the online setting, the adaptive setting, and some robust algorithms.
2. Graph minor theory, by Robertson and Seymour, is perhaps the deepest theory in all of Discrete Mathematics, and it also creates the deepest discrete algorithms. But this theory applies only for undirected graphs. In this proposal, we will extend graph minor theory to digraphs.
3. Graph Coloring is one of the fundamental problems in graph theory and algorithms. In this proposal, we will work on graph coloring problems for planar graphs (i.e., the four color theorem), and graphs on a surface. Our special focus would be to obtain a faster algorithm for these problems.