*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Hardness and Tractability for Structured Numerical Problems
Peng Zhang
School of Computer Science
College of Computing
Georgia Institute of Technology
Date: Monday, Aug 20, 2018
Time: 11am (EST)
Location: KACB 2100
Committee:
--------------
Dr. Richard Peng (Advisor), School of Computer Science, Georgia Institute of Technology
Dr. Edmond Chow, School of Computational Science and Engineering, Georgia Institute of Technology
Dr. Petros Drineas, Department of Computer Science, Purdue University
Dr. Milena Mihail, School of Computer Science, Georgia Institute of Technology
Dr. Santosh Vempala, School of Computer Science, Georgia Institute of Technology
Abstract:
--------------
We study structured linear systems and structured linear programs (LPs) from both algorithm and complexity perspectives. These structured problems commonly arise in combinatorial optimization, machine learning, and operation research. Many of them can be solved significantly faster than general linear systems or linear programs by using additional structures.
First, we consider linear systems in matrices which form a slightly larger class of graph Laplacians, referred to as Graph-Structured Block Matrices (GSBMs). In contrast to the existing nearly-linear time solvers for graph Laplacians (Spielman-Teng 2004) and its generalizations (Kyng et al 2016, Cohen et al 2017 and 2018), we prove hardness results for GSBMs: approximately solving linear systems in GSBMs is equally hard as approximately solving arbitrary linear systems. Building upon linear system based hardness assumptions, we then establish conditional lower bounds for packing and covering LPs, which are a special case of LPs with non-negative coefficients, constants and variables.
On the algorithmic side, we obtain an asymptotically faster solver for linear systems in 3-D trusses with additional geometric structures. General truss matrices are GSBMs. Moreover, we design a parallel algorithm for approximately solving mixed packing and covering LPs, which improves the algorithm by Young (2001).
