AF: EAGER: Algorithms in Linear Algebra and Optimization

Schulman博士的研究将解决计算机科学中两个至关重要的问题：(1)强多项式时间的线性规划和(2)对角平衡的矩阵预处理。线性规划的强多项式时间算法将是现实领域复杂性理论的一个突破。它可能会导致对更难类型的凸规划（例如，半定）的改进算法，这些算法（尽管在多项式时间内）目前非常慢。更好的矩阵预处理算法有可能显著改善线性代数软件包。

Dr. Schulman's research will tackle two problems of central importance in computer science: (1) Linear programming in strongly polynomial time and (2) Matrix pre-conditioning by diagonal balancing. A strongly polynomial-time algorithm for linear programming would be a breakthrough in complexity theory over the real field. It may lead to improved algorithms for harder types ofconvex programming (e.g., semidefinite) which (albeit in polynomial time) are currently prohibitively slow. Better algorithms for matrix preconditioning have the potentially to significantly improve linear algebra software packages.