10
$\begingroup$

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

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

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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