Lower bounds for linear degeneracy testing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for linear degeneracy testing

Full text

Pdf (149 KB)

Source

Journal of the ACM (JACM) archive
Volume 52 , Issue 2 (March 2005) table of contents

Pages: 157 - 171

Year of Publication: 2005

ISSN:0004-5411

Authors

Nir Ailon	Princeton University, Princeton, New Jersey
Bernard Chazelle	Princeton University, Princeton, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 45, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1059513.1059515 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Arkin, E., Chiang, Y.-J., Held, M., Mitchell, J., Sacristan, V., Skiena, S., and Yang, T.-C. 1998. On minimum-area hulls. Algorithmica 21, 119--136.
	2	Barequet, G., and Har-Peled, S. 2001. Polygon containment and translational min-hausdorff-distance between segment sets are 3sum-hard. Int. J. Comput. Geom. App. 11, 465--474.
	3	Antonio Hernández Barrera, Finding an o(n2 log n) Algorithm Is Sometimes Hard, Proceedings of the 8th Canadian Conference on Computational Geometry, p.289-294, August 12-15, 1996
	4	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
	5	Anders Björner , László Lovász , Andrew C. C. Yao, Linear decision trees: volume estimates and topological bounds, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.170-177, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129730]
	6	Prosenjit Bose , Marc J. van Kreveld , Godfried T. Toussaint, Filling Polyhedral Molds, Proceedings of the Third Workshop on Algorithms and Data Structures, p.210-221, August 11-13, 1993
	7	Mark de Berg , Marko M. de Groot , Mark H. Overmars, Perfect binary space partitions, Computational Geometry: Theory and Applications, v.7 n.1-2, p.81-91, Jan. 1997 [doi>10.1016/0925-7721(95)00045-3]
	8	Martin Dietzfelbinger, Lower bounds for sorting of sums, Theoretical Computer Science, v.66 n.2, p.137-155, 20 Aug. 1989 [doi>10.1016/0304-3975(89)90132-1]
	9	Dobkin, D., and Lipton, R. 1979. On the complexity of computations under varying set of primitives. J. Comput. Syst. Sci. 18, 86--91.
	10	Erickson, J. 1999a. Lower bounds for linear satisfiability problems. Chi. J. Theoret. Comput. Sci. 8.
	11	Jeff Erickson, New Lower Bounds for Convex Hull Problems in Odd Dimensions, SIAM Journal on Computing, v.28 n.4, p.1198-1214, Aug. 1999 [doi>10.1137/S0097539797315410]
	12	Erickson, J., and Seidel, R. 1995. Better lower bounds on detecting affine and spherical degeneracies. Disc. Comput. Geom. 13, 41--57.
	13	Fredman, M. 1976. How good is the information theory bound in sorting. Theoret. Comput. Sci. 1, 355--361.
	14	Anka Gajentaan , Mark H. Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry: Theory and Applications, v.5 n.3, p.165-185, Oct. 1995 [doi>10.1016/0925-7721(95)00022-2]
	15	Dima Grigoriev , Marek Karpinski , Friedhelm Meyer auf der Heide , Roman Smolensky, A lower bound for randomized algebraic decision trees, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.612-619, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238011]
	16	Grigoriev, D., Karpinski, M., and Vorobjov, N. 1997. Lower bound on testing membership to a polyhedron by algebraic decision and computation trees. Disc. Comput. Geom. 17, 191--215.
	17	MacWilliams, F., and Sloane, N. 1977. The Theory of Error Correcting Codes. North Holland.
	18	Matousek, J. 1995. On geometric optimization with few violated constraints. Disc. Comput. Geom. 14, 365--384.
	19	S. Meiser, Point location in arrangements of hyperplanes, Information and Computation, v.106 n.2, p.286-303, Oct. 1993 [doi>10.1006/inco.1993.1057]
	20	Friedhelm Meyer auf der Heide, A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem, Journal of the ACM (JACM), v.31 n.3, p.668-676, July 1984 [doi>10.1145/828.322450]
	21	Nagura, J. 1952. On the interval containing at least one prime number. Proc. Japan Acad. 28, 177--181.
	22	Steele, M., and Yao, A. 1982. Lower bounds for algebraic decision trees. J. Alg. 3, 1--8.
	23	Andrew Chi-Chih Yao, Algebraic decision trees and Euler characteristics, Theoretical Computer Science, v.141 n.1-2, p.133-150, April 17, 1995 [doi>10.1016/0304-3975(94)00082-T]
	24	Andrew Chi-Chih Yao, Decision tree complexity and Betti numbers, Journal of Computer and System Sciences, v.55 n.1, p.36-43, Aug. 1997 [doi>10.1006/jcss.1997.1495]
	25	Yao, A. 2000. Why I'm an optimist. In DIMACS Workshop on Intrinsic Complexity of Computation. 10--13.