# Lower bounds for linear satisfiability problem

In SODA 1995, Jeff Erickson showed lower bounds for linear satisfiability (checking if a some $r$-subset of $n$ real numbers satisfies a linear equation on $r$ variables). The proof method uses infinitesimals and Tarski's transfer principle.

Could someone explain the intuition behind the route taken to prove this bound ? What is the difficulty in coming up with a direct proof like this: "Given a decision tree which takes real numbers, here's how we can construct an adversarial input" ?

• I assume you refer to this document: portal.acm.org/citation.cfm?id=313772 – MRA Aug 27 '10 at 15:19
• edited appropriately – Suresh Venkat Aug 27 '10 at 16:17
• Yes, that's the paper I'm referring to. @suresh thanks – Jagadish Aug 27 '10 at 17:28