Linear Algebraic Techniques in Algorithmic Graph Theory

基本图问题的算法是计算机科学和工程中的重要工具。在过去的几十年里，人们进行了大量的研究来开发高效的算法，其中大多数基于组合技术。近年来，新的线性代数技术得到了发展，在这些基本问题上取得了惊人的重大进展。我以前的研究发展了线性代数技术，为图问题设计更好的近似算法和更快的精确算法。我计划继续这条正在进行的研究路线，并确定了三个有希望的研究方向。

Algorithms for fundamental graph problems are important tools in computer science and engineering.  Extensive research has been done in the past decades to develop efficient algorithms, most of them based on combinatorial techniques.  In recent years, new linear algebraic techniques have been developed to make surprising and significant progress in these fundamental problems.  My previous research develops linear algebraic techniques to design both better approximation algorithms and faster exact algorithms for graph problems.  I plan to continue this line of ongoing research and have identified three promising directions to investigate.