An exponential lower bound for depth 3 arithmetic circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An exponential lower bound for depth 3 arithmetic circuits

Full text

Pdf (579 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: 577 - 582

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Dima Grigoriev	Dept. of Computer Science and Mathematics, Penn State University, University Park
Marek Karpinski	Dept. of Computer Science, University of Bonn, 53117, Bonn

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): 17, Citation Count: 9

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.276872 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.

	G82	D. Grigoriev, Lower Bounds in Algebraic Complexity, J. Soviet Math., 29 (1985), pp. 1388-1425.
	H77	R. Hartshorne, Algebraic Geometry, Springer Verlag, 1977.
	L75	L. Lov~sz, On the Ratio of Optimal Integral and Rational Covers, Discrete Mathematics, 13 (1975), pp. 383-390.
	N91	Noam Nisan, Lower bounds for non-commutative computation, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.410-418, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103462]
	L84	S. Lang, Algebra (2nd Edition), Addison- Wesley, 1984.
	NW95	N. Nisan , A. Wigderson, Lower bounds on arithmetic circuits via partial derivatives, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.16, October 23-25, 1995
	R87	A. Razborov, Lower Bounds on the Size of Bounded Depth Circuits over a Complete Basis with Logical Addition, Math. Notes, 41 (1987), pp. 333-338.
	R98	A. R~borov, Personal communication, 1998.
	S87	R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
	S73	V. Strassen, Die Berechnungskomplexit~t yon Elementarsymmetrischen Funktionen und yon Interpolationskoeffizienten, Numer. Math. 20 (1973), pp. 238-251.
	S76	V. Strassen, Computational Complexity over Finite Fields, SIAM J. Comput. 5 (1976), pp. 324-331.
	V79	L. G. Valiant, Completeness classes in algebra, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.249-261, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804419]

CITED BY 9

	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
	Neeraj Kayal , Nitin Saxena, Polynomial Identity Testing for Depth 3 Circuits, Computational Complexity, v.16 n.2, p.115-138, May 2007
	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
	Amir Shpilka, Affine projections of symmetric polynomials, Journal of Computer and System Sciences, v.65 n.4, p.639-659, December 2002
	Ran Raz , Amir Shpilka, Lower bounds for matrix product, in bounded depth circuits with arbitrary gates, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.409-418, July 2001, Hersonissos, Greece
	Zeev Dvir , Amir Shpilka , Amir Yehudayoff, Hardness-randomness tradeoffs for bounded depth arithmetic circuits, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	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
	Anna Bernasconi , Carsten Damm , Igor Shparlinski, Circuit and decision tree complexity of some number theoretic problems, Information and Computation, v.168 n.2, p.113-124, Aug. 1, 2001
	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