Lower bounds for non-commutative computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for non-commutative computation

Full text

Pdf (792 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 410 - 418

Year of Publication: 1991

ISBN:0-89791-397-3

Author

Noam Nisan

Hebrew Univ., Jerusalem, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 36, Citation Count: 10

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/103418.103462 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	L. Babai and P. Frankl, L#near algebra methods #n combinatorics, 1988.
	2	R.B. Boppana and M. Sipser, The complexity offinite functtons, to appear in Handbook of computer science.
	3	Joachim von zur Gathen, Algebraic complexity theory, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
	4	L. Hyafil, The power of commutativity, 18th FOCS, 171-74, 1977.
	5	Laurent Hyafil, On the parallel evaluation of multivariate polynomials, Proceedings of the tenth annual ACM symposium on Theory of computing, p.193-195, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804347]
	6	M. Jerrum and M. Snir, Some exact complexity results for straight-line computatzons over semzmngs, Univ. of Edinburgh CRS-58- 80, 1980.
	7	L. Lovasz, Commune, carton complexity: survey, 1989.
	8	Gary L. Miller , Vijaya Ramachandran , Erich Kaltofen, Efficient parallel evaluation of straight-line code and arithmetic circuits, SIAM Journal on Computing, v.17 n.4, p.687-695, August 1988 [doi>10.1137/0217044]
	9	L. Valiant, Negation can be exponentzally powerful, 1979.
	10	L. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff, Fa#t parallel computatzon of polynomials using few processors, Siam J. Comp. 12:641-44, 1983.
	11	V. Strassen, Vermeidung yon divzszonen, J. Reine Angew Math., 264:184-202, 1973.
	12	C.P. Schnorr, A lower bound on the number of additions in monotone computations, TCS 2:305-315, 1976.
	13	E. Shamir and M. Snir, Lower bounds on the number of multiphcalions and the number of additions in monotone computations, IBM RC-6757, 1977.
	14	E. Shamir and M. Snir, On the depth complexity of formulas, Math. Systems theory, 13:301-322, 1980.
	15	S. Winograd, On the number of multzplicatzons necessary to compute certain functions, Comm. on Pure and Appl. Math., 23:165- 179, 1970.
	16	Mihalis Yannakakis, Expressing combinatorial optimization problems by linear programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.223-228, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62232]

CITED BY 10

	Eric Allender , Jia Jiao, Depth reduction for noncommutative arithmetic circuits, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.515-522, May 16-18, 1993, San Diego, California, United States
	Meena Mahajan , V. Vinay, A combinatorial algorithm for the determinant, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.730-738, January 05-07, 1997, New Orleans, Louisiana, United States
	Dima Grigoriev , Marek Karpinski, An exponential lower bound for depth 3 arithmetic circuits, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.577-582, May 24-26, 1998, Dallas, Texas, United States
	Steve Chien , Lars Rasmussen , Alistair Sinclair, Clifford algebras and approximating the permanent, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Amir Shpilka, Affine projections of symmetric polynomials, Journal of Computer and System Sciences, v.65 n.4, p.639-659, December 2002
	Steve Chien , Lars Rasmussen , Alistair Sinclair, Clifford algebras and approximating the permanent, Journal of Computer and System Sciences, v.67 n.2, p.263-290, September 2003
	Ran Raz, Multi-linear formulas for permanent and determinant are of super-polynomial size, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.633-641, June 13-16, 2004, Chicago, IL, USA
	Zeev Dvir , Amir Shpilka, Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Ran Raz, Elusive functions and lower bounds for arithmetic circuits, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Ran Raz, Multi-linear formulas for permanent and determinant are of super-polynomial size, Journal of the ACM (JACM), v.56 n.2, p.1-17, April 2009