On the space complexity of linear programming with preprocessing

Yael Tauman Kalai, Ran Raz, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

It is well known that Linear Programming is P-complete, with a log-space 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 x, subject to Ax ≥b; x €2 Rd, 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 log-space reduction, thus showing that no(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 nonnegative, we restrict ourselves to the case where x ≥0 and c ≥0. We show that (even in this possibly easier case) approximating the value of max c 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 nosignaling 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.

Original languageEnglish (US)
Title of host publicationITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery, Inc
Pages293-300
Number of pages8
ISBN (Electronic)9781450340571
DOIs
StatePublished - Jan 14 2016
Event7th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016 - Cambridge, United States
Duration: Jan 14 2016Jan 16 2016

Publication series

NameITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science

Other

Other7th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016
CountryUnited States
CityCambridge
Period1/14/161/16/16

Keywords

  • Linear programming
  • P-completeness
  • Preprocessing
  • Space complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the space complexity of linear programming with preprocessing'. Together they form a unique fingerprint.

  • Cite this

    Kalai, Y. T., Raz, R., & Regev, O. (2016). On the space complexity of linear programming with preprocessing. In ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (pp. 293-300). (ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science). Association for Computing Machinery, Inc. https://doi.org/10.1145/2840728.2840750