<p>Indeed, the main argument <strong>is</strong> 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. </p>

CC BY-SA 2.5
2010-08-27T17:43:11.283Z
2010-08-27T17:43:11.283Z
Suresh Venkat
<p>I <em>strongly</em> suggest reading the more recent <a href="http://portal.acm.org/citation.cfm?id=1059513.1059515" rel="nofollow">followup paper by Ailon and Chazelle</a>, which avoids the whole infinitesimal issue entirely.  If you want to stick with my paper, please read the journal version (<a href="http://cjtcs.cs.uchicago.edu/articles/1999/8/contents.html" rel="nofollow">Chicago J Theoretical Computer Science 1999</a>).  The SODA version has a major bug in Section 5, and (I think) the journal version explains the main proof much more clearly.</p>

CC BY-SA 2.5
2010-08-28T01:55:56.247Z
2010-08-28T16:11:21.370Z
2010-08-28T16:11:21.370Z
Jeffε
<p>In <a href="http://portal.acm.org/citation.cfm?id=313772" rel="nofollow">SODA 1995</a>, 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 <a href="http://en.wikipedia.org/wiki/Transfer_principle" rel="nofollow">transfer principle</a>. </p>

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

CC BY-SA 2.5
2010-08-27T15:19:24.543Z
I assume you refer to this document: http://portal.acm.org/citation.cfm?id=313772
MRA
CC BY-SA 2.5
2010-08-27T16:17:25.653Z
edited appropriately
Suresh Venkat
CC BY-SA 2.5
2010-08-27T17:28:09.397Z
Yes, that's the paper I'm referring to. 

@suresh thanks
Jagadish
<cg.comp-geom><lower-bounds><algebraic-complexity>
Lower bounds for linear satisfiability problem
Jagadish
# Lower bounds for linear satisfiability problem

(Asked by: username_0 on 2010-08-27)

In [SODA 1995](http://portal.acm.org/citation.cfm?id=313772), 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](http://en.wikipedia.org/wiki/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" ?

**Tags:** cg.comp-geom, lower-bounds, algebraic-complexity

> **Comments:**
> **username_1**: I assume you refer to this document: http://portal.acm.org/citation.cfm?id=313772  
> **username_2**: edited appropriately  
> **username_0**: Yes, that's the paper I'm referring to.   @suresh thanks  

---

## 2 answers

### Answer by username_3 on 2010-08-28. Score: 15 | Accepted answer

I *strongly* suggest reading the more recent [followup paper by Ailon and Chazelle](http://portal.acm.org/citation.cfm?id=1059513.1059515), 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](http://cjtcs.cs.uchicago.edu/articles/1999/8/contents.html)). The SODA version has a major bug in Section 5, and (I think) the journal version explains the main proof much more clearly.


---

### Answer by username_2 on 2010-08-27. Score: 2

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.


---

