Lower bounds for linear degeneracy testing

Nir Ailon, Bernard Chazelle

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

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 languageEnglish (US)
Pages (from-to)554-560
Number of pages7
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Jan 1 2004
EventProceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States
Duration: Jun 13 2004Jun 15 2004

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Computational Geometry
  • Linear Decision Trees
  • Lower Bounds

Fingerprint Dive into the research topics of 'Lower bounds for linear degeneracy testing'. Together they form a unique fingerprint.

Cite this