Linear decision trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear decision trees: volume estimates and topological bounds

Full text

Pdf (682 KB)

Source

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

Victoria, British Columbia, Canada

Pages: 170 - 177

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Anders Björner	Royal Institute of Technology, Stockholm, Sweden S-100 44
László Lovász	Eötvös Loránd University, Budapest, Hungary H-1088, Princeton University, Princeton, NJ
Andrew C. C. Yao	Princeton University, Princeton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 39, Citation Count: 14

Additional Information:

references cited by index terms review 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/129712.129730 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.

	Ba	K. BaH: Volume ratios and a reverse isoperimetric inequality (preprint 1991).
	Bj	A. Björner, Topological methods, Handbook of combinatorics (vol. 2), MIT Press, Cambridge, MA, 1996
	BO	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]
	DL	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
	GM	M. Goresky and R. MacPherson: Stratified Morse Theory, Ergebnisse, Band 14, Springer- Verlag, Berlin (1988)
	Mi	J. Milnor: On the Betti numbers of real algebraic varieties, Proc. Amer. Math. Soc. 15 (1964) 275-280.
	Mu	J.R. Munkres: Elements of Algebraic Topology, Addison-Wesley, Menlo Park (1984).
	MH	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]
	S	R P Stanley, Enumerative combinatorics, Wadsworth Publ. Co., Belmont, CA, 1986
	SY	M. Steele and A. Yao, Lower bounds for algebraic decision trees, J. Algorithms 3 (1982), 1-8.
	Th	R. Thorn: Sur l'homologie des vari#t#s alg#briques r#elles, in: Differential and Algebraic Topology (ed. S. S. Cairns), Princeton Univ. Press, Princeton (1965).
	Tu	P. Tur~n: Eine neue Methode in der Analysis und deren Anwendungen, Akad. Kiad6, Budapest (1953).

CITED BY 14

	Andrew Chi-Chih Yao, Decision tree complexity and Betti numbers, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.615-624, May 23-25, 1994, Montreal, Quebec, Canada
	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
	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
	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
	Ketan Mulmuley, Lower bounds for parallel linear programming and other problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.603-614, May 23-25, 1994, Montreal, Quebec, Canada
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Rudolf Fleischer, Decision trees: old and new results, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.468-477, May 16-18, 1993, San Diego, California, 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 , 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
	Nir Ailon , Bernard Chazelle, Lower bounds for linear degeneracy testing, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Michelle L. Wachs, Whitney Homology of Semipure Shellable Posets, Journal of Algebraic Combinatorics: An International Journal, v.9 n.2, p.173-207, March 1999
	Nir Ailon , Bernard Chazelle, Lower bounds for linear degeneracy testing, Journal of the ACM (JACM), v.52 n.2, p.157-171, March 2005
	Andreas Blass , Bruce E. Sagan, Characteristic and Ehrhart Polynomials, Journal of Algebraic Combinatorics: An International Journal, v.7 n.2, p.115-126, March 1998
	Martin Aigner, The $k$-Equal Problem, Combinatorics, Probability and Computing, v.14 n.1, p.17-24, January 2005

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
I. Computing Methodologies
I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
I.1.2 Algorithms
Subjects: Analysis of algorithms

General Terms:
Algorithms, Performance, Theory

REVIEW

"Prakash Ramanan : Reviewer"

Many combinatorial and geometric decision problems reduce to the following membership testing problem. Let P be a fixed region in Rⁿ ; given < more...

Collaborative Colleagues:

Anders Björner: colleagues

László Lovász: colleagues

Andrew C. C. Yao: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player