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" ?

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

2 Answers 2


I strongly suggest reading the more recent followup paper by Ailon and Chazelle, which avoids the whole infinitesimal issue entirely. If you want to stick with my paper, please read the journal version (Chicago J Theoretical Computer Science 1999). The SODA version has a major bug in Section 5, and (I think) the journal version explains the main proof much more clearly.


Indeed, the main argument is to construct a decision tree and design adversarial input, but there are technical issues with doing this that the infinitesimals avoid. Look at the discussion at the bottom of page 2 first column, and continuing on, which explains this fairly clearly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.