Overview

Graph Coloring and the four-color theorem

One of the oldest problems in graph theory was the celebrated four-color conjecture on coloring planar graphs, which was raised in 1852. Even now, it is difficult to say that the essence of the four-color coloring of a planar graph has been clarified. Furthermore, from an algorithmic point of view, to 4-color a planar graph faster, it is necessary to use the global situation of planar graphs, but the relationship between this global property and 4-coloring has not yet been clarified. We will investigate these issues.

Combinatorial optimization

It has broad application to problems in the allocation of scarce resources, logistics, and network planning, as well as to areas of science, economics, and engineering. We propose a line of research centered on computational aspects of discrete optimization, aiming to deliver improved techniques for solving problems in practice and to test possible limits of computing power.

Quantum algorithms and information

One of the main challenges in quantum computing is developing new quantum algorithms and discovering new applications for which quantum computers can offer speedups—especially exponential speedups—over classical computers. We will develop quantum algorithms for new computer science problems and important physics problems.

International Joint Research System