Fine-Grained Complexity and Algorithms for Structured Linear Equations and Linear Programs

Abstract

Linear Equations (LEs) and Linear Programs (LPs) are fundamental tools in scientific research and practical applications, with widespread use in optimization, engineering, and data analysis. Many real-world problems exhibit specific structural properties, enabling structured problems to be solved significantly faster than general-purpose solvers for LEs and LPs. This thesis explores several structured LEs and LPs from both complexity and algorithmic perspectives.

For LPs, we investigate the computational complexity of the two-commodity flow (2CF) problem, a natural generalization of the well-studied single-commodity flow (i.e., maximum flow) problem. Both 2CF and maximum flow problems can be formulated as LPs, each defining a distinct family of structured LPs. Given the success of efficient algorithms for maximum flow and the structural similarities between the two problems, it was widely conjectured that 2CF could also be solved more efficiently than general LPs. Contrary to this belief, we prove that solving 2CF — either exactly or approximately to high accuracy — is as computationally hard as solving general LPs. We prove this by giving a nearly-linear time reduction that encodes any LP as a 2CF problem on a sparse directed graph with only a polylogarithmic blow-up in problem size. Furthermore, careful error analysis guarantees that any approximate 2CF solution can be mapped back into an approximate LP solution with only a polynomial increase in error.

For LEs, we focus on systems of linear equations whose coefficient matrices are combinatorial Laplacians, a class of generalized graph Laplacians that arise in higher-dimensional problems on simplicial complexes. Combinatorial Laplacians play a crucial role in homology (a central tool in topology), and have various applications in data analysis and physical modeling problems. While nearly-linear time solvers are known for graph Laplacians, efficient solvers for combinatorial Laplacians are only known for restricted classes of simplicial complexes. By constructing a nearly-linear time reduction from general LEs to combinatorial Laplacians of 2-complexes, we show that solving linear equations in combinatorial Laplacians is computationally as hard as solving general LEs. Notably, our reduction preserves problem sparsity up to polylogarithmic factors.

Finally on the algorithmic side, despite our hardness results for combinatorial Laplacians, we demonstrate that imposing geometric structure on simplicial complexes can lead to substantial computational improvements. In particular, we develop sub-quadratic time algorithms for approximately solving LEs in 1-Laplacians (i.e., 1-dimensional combinatorial Laplacians) on well-shaped simplicial complexes up to high accuracy.