TY - GEN

T1 - Lower bounds for linear satisfiability problems

AU - Erickson, Jeff

N1 - Funding Information:
*Portions of this research were done at the NSF Regional Geometry Institute at Smith College, Northampton, MA, July 1993. This research was partially supported by NSF Presidential Young Investigator grant CCR-9058440. tcomputer Science Division, University of California, Berke-

PY - 1995/1/22

Y1 - 1995/1/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85039802428&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85039802428&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85039802428

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 388

EP - 395

BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

PB - Association for Computing Machinery

T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

Y2 - 22 January 1995 through 24 January 1995

ER -