Lower bounds for linear satisfiability problems

Chicago Journal of Theoretical Computer Science 1999(8), 1999.

Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 388-395, 1995.

We prove an Omega(nceiling{r/2}) lower bound for the following problem: For some fixed linear equation in r variables, given a set of n real numbers, do any r of them satisfy the equation? Our lower bound holds in a restricted linear decision tree model, in which each decision is based on the sign of an arbitrary affine combination of r or fewer inputs. In this model, our lower bound is as large as possible. Previously, this lower bound was known only for a few special cases, and only for more specialized models of computation.
          Our lower bound follows from an adversary argument. We show that for any algorithm, there is a corresponding input that contains Omega(nceiling{r/2}) ``critical'' r-tuples, which have the following important property. If the algorithm does not test each critical tuple to see if it satisfies the equation, then the adversary can modify the input, in a way that is undetectable to the algorithm, so that some untested tuple does satisfy the equation. A key step in the proof is the introduction of formal infinitesimals into the adversary input. A theorem of Tarski implies that if we can construct a single input containing infinitesimals that is hard for every algorithm, then for every decision tree algorithm, there exists a corresponding real-valued input which is hard for that algorithm.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 14 Feb 2002