Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard

We study the complexity of approximately solving packing linear programs. In the Real RAM model, it is known how to solve packing LPs with N non-zeros in time Õ(N/ϵ). We investigate whether the ϵ dependence in the running time can be improved. Our first main result relates the difficulty of this problem to hardness assumptions for solving dense linear equations. We show that, in the Real RAM model, unless linear equations in matrices n × n with condition number O(n10) can be solved to ϵ accuracy faster than Õ(n2.01 log(1/ϵ)), no algorithm (1−ϵ)-approximately solves a O(n)×O(n) packing LPs (where N = O(n2)) in time Õ(n2ϵ−0.0003). It would be surprising to solve linear equations in the Real RAM model this fast, as we currently cannot solve them faster than Õ(nω), where ω denotes the exponent in the running time for matrix multiplication in the Real RAM model (and equivalently matrix inversion). The current best bound on this exponent is roughly ω ≤ 2.372. Note, however, that a fast solver for linear equations does not directly imply faster matrix multiplication. But, our reduction shows that if fast and accurate packing LP solvers exist, then either linear equations can be solved much faster than matrix multiplication or the matrix multiplication constant is very close to 2. Instantiating the same reduction with different parameters, we show that unless linear equations in matrices with condition number O(n1.5) can be solved to ϵ accuracy faster than Õ(n2.372 log(1/ϵ)), no algorithm (1 – ϵ)-approximately solves packing LPs in time Õ(n2ϵ−0.067). Thus smaller improvements in the exponent for ϵ in the running time of Packing LP solvers also imply improvements in the current state-of-the-art for solving linear equations. Our second main result relates the difficulty of approximately solving packing linear programs to hardness assumptions for solving sparse linear equations: In the Real RAM model, unless well-conditioned sparse systems of linear equations can be solved faster than Õ((no. non-zeros of matrix) ), no algorithm (1 – ϵ)-approximately solves packing LPs with N non-zeros in time Õ(Nϵ−0.165). This running time of Õ((no. non-zeros of matrix) ) is obtained by the classical Conjugate Gradient algorithm by a standard analysis. Our reduction implies that if sufficiently good packing LP solvers exist, then this long-standing best-known bound on the running time for solving well-conditioned systems of linear equations is sub-optimal1. While we prove results in the Real RAM model, our condition number assumptions ensure that our results can be translated to fixed point arithmetic with (log n)O(1) bits per number.