Collaborative Research: AF:Medium: Structure and Quasi-Polynomial Time Algorithms

About This Grant

Throughout mathematics and computer science there is an over-arching connection between structural and descriptive mathematical statements and efficient algorithms. Here efficient algorithms mean polynomial time algorithms. These are algorithms whose running time scales well with the size of the input data that they are supposed to process. When you double the size of the data, the time taken to process it also get doubled, or at worst multiplied by a fixed constant. Efficient algorithms permeate everything, and so it is of utmost importance to know which problems can and can't be solved efficiently by computers. Yet, for some fundamental problems, such as the Independent Set problem (given a social network, find the largest group of people who do not know each other), researchers have been unable to establish precisely when an efficient algorithm exists and when it does not. Quite recently a lot of progress has been made on this problem, and on other related problems, by considering quasi-polynomial time algorithms instead of polynomial time algorithms. These are algorithms that are almost as efficient as polynomial time algorithms, but not quite. In this project the investigators will build a theory of quasi-polynomial time algorithms for graph problems. This will also lead to new and fundamental descriptive mathematical theorems, especially within the field of graph theory. Despite tremendous effort, a number of fundamental computational problems in algorithmic graph theory still resist classification into polynomial time solvable or NP-hard. On the other hand, there have been a number of recent breakthrough results, many of which were co-authored by the investigators, establishing quasi-polynomial time algorithms for problems for which the existence of polynomial time algorithms remains as a central open problem in the field. The quasi-polynomial time algorithms effectively rule out the possibility of NP-hardness results for the considered problems. These algorithms are built on structural insights specifically tailored to quasi-polynomial time, rather than polynomial time, algorithms. The structure theory underlying quasi-polynomial time graph algorithms is rapidly developing into a research area in and of itself. In this project, the investigators will spearhead the development of this exciting new direction and build the structure theory for quasi-polynomial time graph algorithms. In many important aspects the new structure theory will serve as an analogue of the famous graph minors project for induced minors. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.