Lower bounds for linear satisfiability problems

We prove an Ω(n^⌈/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, out lower bound is as large as possible. Previously, this lower bound was known only for even r, and only for one special case. We also apply reduction arguments to achieve new lower bounds for a number of Hgher-dimensional geometric decision problems. Our lower bounds follow from a relatively simple adversary argument. We use a theorem of Tarski to show that if we can construct a hard input containing infinitesimals, then for every decision tree algorithm, there exists a corresponding set of real numbers which is hard for that algorithm. Furthermore, we argue that it suffices to find a single input with a large number of "collapsible tuples", even if that input is highly degenerate, i.e., there are several subsets that satisfy the equation.