Lower Bounds for Linear Degeneracy Testing

COMPUTER SCIENCE/DISCRETE MATH I
Topic:	Lower Bounds for Linear Degeneracy Testing
Speaker:	Nir Ailon
Affiliation:	Princeton University
Date:	Monday, October 4
Time/Room:	11:15am - 12:15pm/S-101

---

In the late nineties Erickson proved a remarkable lower bound on the decision tree complexity of one of the central problems of computational geometry: given $n$ numbers, do any $r$ of them add up to $0$? His lower bound of $\Omega(n^{\lceil r/2\rceil})$, for any fixed $r$, is optimal if the polynomials at the nodes are linear and at most $r$-variate. We generalize his bound to $s$-variate polynomials for $s>r$. Erickson's bound decays quickly as $r$ grows and never reaches above pseudo-polynomial: we provide an exponential improvement.

Our arguments are based on three ideas:

(i) a geometrization of Erickson's proof technique;
(ii) the use of error-correcting codes; and
(iii) a tensor product construction for permutation matrices.