James Renegar

I am currently devoting the majority of my research efforts to devising new algorithms for linear programming, i.e., for solving systems of linear inequalities. Unlike the situation for linear equations, surprisingly basic problems remain unresolved for linear inequalities. For example, it is unknown whether there exists an algorithm that can solve a general system of linear inequalities using a number of arithmetic operations that is bounded polynomially in the number of variables and the number of inequalities in the system. By contrast, elementary Gaussian elimination (i.e., high-school mathematics) solves a system of n linear equations in n unknowns in roughly n^3 operations.

I am also interested in devising algorithms for more general problems involving hyperbolic polynomials. (A hyperbolic polynomial p is a real multivariate polynomial for which there exists a vector v such that all univariate polynomials obtained by restricting p to lines in the direction v have only real roots.) These polynomials have played an especially important role in optimization in recent years.