ECCC-Report TR14-170https://eccc.weizmann.ac.il/report/2014/170Comments and Revisions published for TR14-170en-usTue, 11 Aug 2015 19:12:50 +0300
Revision 1
| On the Space Complexity of Linear Programming with Preprocessing |
Yael Tauman Kalai,
Ran Raz,
Oded Regev
https://eccc.weizmann.ac.il/report/2014/170#revision1It is well known that Linear Programming is P-complete, with a logspace reduction. In this work we ask whether Linear Programming remains P-complete, even if the polyhedron (i.e., the set of linear inequality constraints) is a fixed polyhedron, for each input size, and only the objective function is given as input.
More formally, we consider the following problem: maximize $c\cdot x$, subject to $Ax\leq b; x \in \mathbb{R}^d$, where $A,b$ are fixed in advance and only $c$ is given as an input.
We start by showing that the problem remains P-complete with a logspace reduction, thus showing that $n^{o(1)}$-space algorithms are unlikely. This result is proved by a direct classical reduction.
We then turn to study approximation algorithms and ask what is the best approximation factor that could be obtained by a small space algorithm. Since approximation factors are mostly meaningful when the objective function is non-negative, we restrict ourselves to the case where $x \geq 0$ and $c \geq 0$.
We show that (even in this possibly easier case) approximating the value of max $c\cdot x$ (within any polynomial factor) is P-complete with a polylog space reduction, thus showing that $2^{(\log n)^{o(1)}}$-space approximation algorithms are unlikely.
The last result is proved using a recent work of Kalai, Raz, and Rothblum, showing that every language in P has a no-signaling multi-prover interactive proof with poly-logarithmic communication complexity. To the best of our knowledge, our result gives the first space hardness of approximation result proved by a PCP-based argument.Tue, 11 Aug 2015 19:12:50 +0300https://eccc.weizmann.ac.il/report/2014/170#revision1
Paper TR14-170
| On the Space Complexity of Linear Programming with Preprocessing |
Yael Tauman Kalai,
Ran Raz
https://eccc.weizmann.ac.il/report/2014/170Linear Programs are abundant in practice, and tremendous effort has been put into designing efficient algorithms for such problems, resulting with very efficient (polynomial time) algorithms. A fundamental question is: what is the space complexity of Linear Programming?
It is widely believed that (even approximating) Linear Programming requires a large space. Specifically, it was shown that (approximating) Linear Programming is P complete with a logspace reduction, thus showing that $n^{o(1)}$-space algorithms for (approximating) Linear Programming are unlikely.
We show that (approximating) Linear Programming is likely to have a large space complexity, even if we allow a preprocessing phase that takes the polyhedron as input and runs in unbounded time and space. Specifically, we prove that (approximating) Linear Programming with such ``preprocessing'' is P complete with a poly-logarithmic space and quasi-polynomial time reduction, thus showing that $2^{(\log n)^{o(1)}}$-space algorithms for Linear Programming with ``preprocessing'' are unlikely.
We obtain our result using a recent work of Kalai, Raz and Rothblum, showing that every language in P has a no-signalling multi-prover interactive proof with poly-logarithmic communication complexity. To the best of our knowledge, this is the first space hardness of approximation result proved by a PCP based argument.Wed, 10 Dec 2014 05:48:25 +0200https://eccc.weizmann.ac.il/report/2014/170