TY - GEN
T1 - Lower bounds for linear satisfiability problems
AU - Erickson, Jeff
N1 - *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 -