### Abstract

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 Ω(n^{⌈r/2⌉}, 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.

Original language | English (US) |
---|---|

Pages (from-to) | 554-560 |

Number of pages | 7 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - Jan 1 2004 |

Event | Proceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States Duration: Jun 13 2004 → Jun 15 2004 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Computational Geometry
- Linear Decision Trees
- Lower Bounds