Lower bounds for linear satisfiability problems

Abstract:
We prove an Omega(n^ceiling{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(n^ceiling{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.