Decision tree complexity and Betti numbers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Decision tree complexity and Betti numbers

Full text

Pdf (801 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 615 - 624

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Andrew Chi-Chih Yao

Department of Computer Science, Princeton University, Princeton, New Jersey

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 16, Citation Count: 8

Additional Information:

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/195058.195414 What is a DOI?

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.

	Be83	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]
	Bj92	A. BjSrner, "Subspace arrangements," in Proceedings of the 1st European Congress of Mathematics, Paris, 1992, edited by A. Joseph and R. Rentschler, Birkhaiiser, Basel-Boston, to appear.
	BL92	A. BjSrner and L. Lov#z, "Linear decision trees, subspace arrangements and MSbius functions," preprint, 1992.
	BLY92	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]
	BW92	A. BjSrner and V. Welker, "The homology of "k-equal" manifolds and related partition lattices," Report No. 39, 1991/92, Institute Mittag-Leftter, Stockholm.
	BR91	R. Brualdi and H. Ryser, Computational Matrix Theory, Cambridge University Press, Cambridge, 1991.
	DL75	David P. Dobkin , Richard J. Lipton, On the complexity of computations under varying sets of primitives, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.110-117, May 20-23, 1975
	GM88	M. Goresky and R. MacPherson, Stratified Morse Theory, Springer-Verlag, New York, 1988.
	GKV93	D. Grigoriev, M. Karpinski, and N. Vorobjov, "Complexity lower bounds on testing membership to a polyhedron by algebraic decision trees," preprint, 1993.
	Ha48	M. Hall Jr., "Distinct representatives of subsets," Bulletin of the American Mathematical Society 54 (1948), 958-961.
	Hi75	H. Hironaka, "Triangulation of algebraic sets," in Proceedings of Symposia in Pure Mathematics, Volume 29 (1975), American Mathematical Society, 165-185.
	HS93	G. Hotz and J. Sellen, "On algebraic computation trees and Betti numbers," Technical Report No. 10/93, Sonderforschungsbereich 124, Saarbruecken/Kaiserslautern, Germany.
	Lu90	A. Lubiw, "A RAM lower bound for the integer distinctness problem," preprint, 1990.
	Mi64	j. Milnor, "On the Betti numbers of real varieties," Proc. Amer. Math. Soc. 15 (1964), 275-280.
	OI51	O.A. Oieinik, "Estimates of the Betti numbers of real algebraic hypersurfaees," Mat. Sbornik (N. S.) 28 (1951), 635-640 (in Russian).
	OP49	O.A. Oleinik and I.B. Petrovsky, "On the topology of real algebraic surfaces," Izv. Akad. Nauk SSSR 13 (1949), 389-402 (in Russian). (Transl. Amer. Math. Soc, (1) 7 (1962), 399-4 7.)
	Ro88	J. Rotman, An Introduction to Algebraic Topology, Springer-Verlag, New York, 1988.
	St86	R P Stanley, Enumerative combinatorics, Wadsworth Publ. Co., Belmont, CA, 1986
	SY82	M. Steele and A. Yao, "Lower bounds for algebraic decision trees," 3". Algorithms 3 (1982), 1-8.
	Th65	R. Thom, "Sur l'homologie des varidtds algdbriques rdelles," in Differential and Algebraic Topology, edited by S. S. Cairns, Princeton University Press, Princeton, 1965.
	Y92	A. Yao, "Algebraic decision trees and Euler characteristics," Proceedings of 33rd FOCS, October 1992, 268-277.

CITED BY 8

	Marie-Françoise Roy , Nicolai Vorobjov, Computing the complexification of a semi-algebraic set, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.26-34, July 24-26, 1996, Zurich, Switzerland
	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
	Dima Grigoriev , Marek Karpinski , Nicolai Vorobjov, Lower bounds on testing membership to a polyhedron by algebraic decision trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.635-644, May 23-25, 1994, Montreal, Quebec, Canada
	Jeff Erickson, Lower bounds for linear satisfiability problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.388-395, January 22-24, 1995, San Francisco, California, United States
	Saugata Basu, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.408-417, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	D. Grigoriev, Randomized complexity lower bounds, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.219-223, May 24-26, 1998, Dallas, Texas, United States
	Dima Grigoriev , Marek Karpinski, Randomized Ω(n²) lower bound for knapsack, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.76-85, May 04-06, 1997, El Paso, Texas, United States
	Nina Amenta , Thomas J. Peters , Alexander C. Russell, Computational topology: ambient isotopic approximation of 2-manifolds, Theoretical Computer Science, v.305 n.1-3, p.3-15, 18 August 2003