Lower bounds for linear degeneracy testing

Nir Ailon, Bernard Chazelle

Research output: Contribution to journalReview articlepeer-review

30 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)157-171
Number of pages15
JournalJournal of the ACM
Volume52
Issue number2
DOIs
StatePublished - 2005

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

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