Published by MIT Press. Copyright 1999 Massachusetts Institute of Technology.
Your institution may already be a subscriber to CJTCS. If not, please subscribe.
We prove an OMEGA(n^(ceiling(r/2))) lower bound for the following problem: For some fixed linear equation in r variables, given 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 linear 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 in more specialized models of computation.
Our lower bound follows from an adversary argument. We show that for
any algorithm, there is a input that contains OMEGA(n^(ceiling(r/2)))
``critical'' r-tuples, which have the following important property.
None of the critical tuples satisfies the equation; however, if the
algorithm does not directly test each critical tuple, then the
adversary can modify the input, in a way that is undetectable to the
algorithm, so that some untested tuple