Lower bounds for linear satisfiability problems

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Electronic)0898713498
StatePublished - Jan 22 1995
Externally publishedYes
Event6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States
Duration: Jan 22 1995Jan 24 1995

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Lower bounds for linear satisfiability problems'. Together they form a unique fingerprint.

Cite this