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

- Preformatted versions of the article
- DVI (96,204 bytes)
**PostScript**(420,322 bytes)- PDF (385,004 bytes)
- Audio by
**AsTeR**(to appear)

- Source materials for custom formatting
**LaTeX**(`cj99-08.tex`, 61,906 bytes)**BIBTeX**(`cj99-08.bib`, 12,156 bytes)- Parameter settings for custom
formatting (
`cjropts.tex`, 165 bytes) - Self citation in
**BIBTeX**(294 bytes)

- Online discussion
- Instructions for Readers

DOI: 10.4086/cjtcs.1999.008

Article 7 Article 9

Volume 1999 Published articles

Article 7 Article 9

Volume 1999 Published articles

Last modified: Sat Mar 20 09:32:31 CST 1999