Access Restriction

Author Ailon, Nir ♦ Chazelle, Bernard
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2005
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Computational geometry ♦ Linear decision trees ♦ Lower bounds
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 $\textit{n}$ numbers, do any $\textit{r}$ of them add up to 0? His lower bound of $Ω(n^{⌈r/2⌉}),$ for any fixed $\textit{r},$ is optimal if the polynomials at the nodes are linear and at most $\textit{r}-variate.$ We generalize his bound to $\textit{s}-variate$ polynomials for $\textit{s}$ > $\textit{r}.$ Erickson's bound decays quickly as $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-03-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 52
Issue Number 2
Page Count 15
Starting Page 157
Ending Page 171

Open content in new tab

   Open content in new tab
Source: ACM Digital Library