Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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 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.
