Overview

Researchers have proposed various techniques for investigating the limits of computation, many of which have been sharpened in depth during the last two decades. We may soon be entering the stage of expecting some big breakthrough results toward understanding the limits of computation.

In this project, we investigate these techniques and relationships among them with the goal of finding the next steps toward a big breakthrough. We propose the following three lines of research, each of which will be conducted by three core research groups (i.e., nine core research groups altogether).

A. Team for pushing the current frontier of research on the limits of computation.

B. Team for investigating the limits of computation by using various algorithmic/optimization techniques (even by using supercomputers).

C. Team for introducing new approaches to and interpretations of the existing techniques for investigating the limits of computation.

We also create a new center — Center for Exploring the Limits of Computation (CELC) — as a center for investigating computational complexity theory by stimulating worldwide collaborations among researchers based on our core research groups, hosting short/long term visitors and postdoctoral researchers, and organizing various meetings and workshops. We welcome researchers working on subjects related to computational complexity theory to join us for various occasions.

>> Please check Complexity Theory Intro. Seminar Series in ELC repository.