Theoretical Computer Science Journal : Lower Bounds for Linear Satis ability Problems
We prove an (ndr=2e) lower bound for the following problem: For some xed 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.
Index of Topic:
- Introduction
- Previous results
- Background and de nitions
- r-linear decision trees
- Ordered elds and in nitesimals
- The main theorem
- The in nitesimal adversary input
- Moving back to the reals
- Removing degeneracies
- Rational and integer problems
- Conclusions and open problems
Download Journal:
http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/linsat.pdf
If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.
Comments
No comments yet.
Leave a comment