Peng Zhang, Rutgers University

Abstract

We study structured systems of linear equations (or linear systems) and structured linear programs, commonly arising from combinatorial optimization, operations research, and so on. Many of them can be solved asymptotically faster than general linear systems and linear programs, by utilizing additional structures. One example is linear systems in graph Laplacians, arising from using the interior-point methods (IPMs) for graph problems such as network flow; Spielman and Teng (2004) showed that Laplacian linear systems can be solved in nearly linear time.

We show that some slight generalizations, such as the linear systems arising from the IPMs for 2-commodity flow and the 2-commodity flow linear programs, are as hard to solve as general linear systems or general linear programs.

This talk is based on joint work with Rasmus Kyng and Ming Ding.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar