Mathematical Sciences: Computational Complexity of Linear Programming and Polynomial Zero Approximation

点击翻译按钮获取中文摘要

Two areas of research are proposed: the computational complexity of approximating zeros of polynomials and systems of polynomials. The main focus of the proposed projects on linear programming is on interior algorithms. The primary objective of these projects is to develop a better understanding ot the mathematics underlying the algorithms so that provably efficient modifications to the algorithms can be made. Both worst-case and average-case measures of efficiency are to be considered. The goal of the proposed projects on polynomial zero approximation is to develop mathematics which is useful for constructing theoretically fast algorithms and useful for proving results regarding the inherent difficulty of the zero approximation problem.