Lower bounds for linear degeneracy testing
Authors:
Open Access
- 1 March 2005
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 52 (2) , 157-171
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.Keywords
This publication has 21 references indexed in Scilit:
- Decision Tree Complexity and Betti NumbersJournal of Computer and System Sciences, 1997
- Perfect binary space partitionsComputational Geometry, 1997
- On a class of O(n2) problems in computational geometryComputational Geometry, 1995
- Algebraic decision trees and Euler characteristicsTheoretical Computer Science, 1995
- Lower bounds for sorting of sumsTheoretical Computer Science, 1989
- A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack ProblemJournal of the ACM, 1984
- Lower bounds for algebraic decision treesJournal of Algorithms, 1982
- On the complexity of computations under varying sets of primitivesJournal of Computer and System Sciences, 1979
- How good is the information theory bound in sorting?Theoretical Computer Science, 1976
- On the interval containing at least one prime numberProceedings of the Japan Academy, Series A, Mathematical Sciences, 1952