Randomized complexity lower bounds

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized complexity lower bounds

Full text

Pdf (688 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 219 - 223

Year of Publication: 1998

ISBN:0-89791-962-9

Author

D. Grigoriev

Departments of Mathematics and Computer Science, The Pennsylvania State University, University Park, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/276698.276745 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.

	1	W. Baur, V. Strassen, The complexity of partial derivatives, Theor. Comput. Sci., Vol. 22, 1983, pp. 317-330
	2	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]
	3	lVl. Ben-Or, Algebraic computation trees in charac{eHs~ tic p :> 0, Proc. IEEE Symp. Found. Comput. Sci., 1994, pp. 534-539.
	4	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]
	5	Peter Bürgisser , Marek Karpinski , Thomas Lickteig, On randomized semi-algebraic test complexity, Journal of Complexity, v.9 n.2, p.231-251, June 1993 [doi>10.1006/jcom.1993.1016]
	6	Dima Grigoriev, Nearly sharp complexity bounds for multiprocessor algebraic computations, Journal of Complexity, v.13 n.1, p.50-64, March 1997 [doi>10.1006/jcom.1997.0436]
	7	Dima Grigoriev, Complexity lower bounds for randomized computation trees over zero characteristic fields, Computational Complexity, v.8 n.4, p.316-329, Dec. 1999 [doi>10.1007/s000370050002]
	8	D,Grlgorle% Randomized Complexity Lower Bounds for Arrangements and Polyhedra, to appear in Discrete and Computational Geometry
	9	Dima Grigoriev , Marek Karpinski, Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees, University of Bonn, 1993
	10	Dima Grigoriev , Marek Karpinski, Lower Bound for Randomized Linear Decision Trees Recognising a Union of Hyperplanes in a Generic Position, University of Bonn, 1994
	11	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 [doi>10.1145/258533.258555]
	12	Grigoriev, M. I<arpinski, R. Smolensky, Randomization and the computational power of analytic and algebraic decision trees, to appear in Computational Complexity, 1997
	13	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]
	14	D. Grigoriev , M. Karpinski , N. Vorobjov, Improved lower bound on testing membership to a polyhedron by algebraic decision trees, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.258, October 23-25, 1995
	15	D, Grigoriev, M. Karpinski, N. Vorobjov, Lower bound on testing membership to a polyhedron by algebraic decision and computation trees, J. Discrete and Computational Geometry, Vol. 17,2, 1997, pp. 191-215.
	16	D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
	17	T. Lickteig, On semialgebraic decision complexity, Preprint TR~0-052 ICSI, Berkeley, 1990.
	18	S, Lang, Algebra, Addison-Wesley, New York, 1965
	19	F Meyer auf der Heide, Simulating probabilistic by deterministic algebraic computation trees, Theoretical Computer Science, v.41 n.2-3, p.325-330, Dec. 1985
	20	R. Moenck, A, Borodin, Fast modular transforms via division Prec. IEEE Syrup. Switching and Automata Theory 1972 pp. 90-96
	21	J. Montana, L. Pardo, Lower bounds for arithmetic networks, Appl. Algebra in Eng. Commun. Comput., Vol. 4, 1993, pp. 1-24.
	22	J. Montana, J.Morais, L.Pardo, Lower bounds for arithmetic network Ih sum of Betti numbers, Appl. Algebra in Eng. Commun. Comput., Vol. 7, 1996, pp. 41-51.
	23	D. Mumford. Algebraic geometry, Springer, 1976.
	24	Udi Manber , Martin Tompa, Probabilistic, nondeterministic, and alternating decision trees (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.234-244, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802197]
	25	I. R. Shafarevich, Basic algebraic geometry, V. 1- Springer, 1994.
	26	M. Steele, A. Yao, Lower bounds for algebraic decision trees, J. Algorithms, Vol. 3, 1982, pp. 1-8.
	27	V. Strassen, Die Berechnungskomplexitaet yon elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math., Vol. 20, 1973, pp. 238- 251.
	28	A.Tarsld, A Decision Method for Elementary Algebra and Geometry, University of California Press, 1951.
	29	A. Yao, Algebraic decision trees and Euler characteristic, Prec. IEEE Syrup. Found. Comput. Sci., 1992, pp. 268-277.
	30	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 [doi>10.1145/195058.195414]