On the complexity of bilinear forms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern

Full text

Pdf (847 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 723 - 732

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Noam Nisan	Institute of Computer Science, Hebrew University of Jerusalem, Israel
Avi Wigderson	Institute of Computer Science, Hebrew University of Jerusalem, Israel

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

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

	AM88	Noga Alon , Wolfgang Maass, Meanders and their applications in lower bounds arguments, Journal of Computer and System Sciences, v.37 n.2, p.118-129, October 1988 [doi>10.1016/0022-0000(88)90002-5]
	B094	A. Borodin, Private communication, 1994.
	BS82	W. Baur, V. Strassen, "The complexity of partial derivatives", Theoretical Com-puter science, 22, pp. 317-330, 1982.
	Ch94	B. Chazelle, "A Spectral Approach to Lower Bounds", Proc. of the 35th FOCS, 1994, to appear.
	DDPW	Danny Dolev , Cynthia Dwork , Nicholas Pippenger , Avi Wigderson, Superconcentrators, generalizers and generalized connectors with limited depth, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.42-51, December 1983 [doi>10.1145/800061.808731]
	Ha86	M. Hall, Combinatorial Theory, John Wiley, 1986.
	L095	S. V. Lokam, "Size-depth tradeoffs for linear transformations", manuscript, 1995.
	M073	Jacques Morgenstern, Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform, Journal of the ACM (JACM), v.20 n.2, p.305-306, April 1973 [doi>10.1145/321752.321761]
	MoW	Jacques Morgenstern, How to compute fast a function and all its derivatives: a variation on the theorem of Baur-strassen, ACM SIGACT News, v.16 n.4, p.60-62, April 1985 [doi>10.1145/382242.382836]
	Pi78	N. Pippenger, "Superconcentrators", SIAM J. C'omput. 6, pp. 298-304, 1978.
	Pi82	N. Pippenger, "Superconcentrators of Depth 2," J. Comp. and Sys. Sci. 24, pp. 82-90, 1982.
	SC80	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	st73	V. Strassen, "Die Berechnungskomplexi-tat vo elementarsymmetrischen Funktio-nen und von Interpolationskoefizienten", Numer. Math. 20, pp. 238-251, 1973.
	SZ94	A. Srinivasan and D. Zuckerman, "Com-puting with Very Weak Random Sources," Proc. of the ,?5th FOG'S, 1994, to appear.
	T080	M. Tompa, "Time Space Tradeoffs for Computing Functions, Using Connec-tivity Properties of Their Circuits," J. Comp. and Sys. Sci, 20, pp. 118-132, 1980.
	Va76	L .G. Valiant, "Graph Theoretic Proper-ties in Computational Complexity," J. Comp. and Sys. Sci. 13, pp. 278-285, 1976.
	Wi65	J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
	WZ93	Avi Wigderson , David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.245-251, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167163]

CITED BY 4

	Satyanarayana V. Lokam, Complexity Lower Bounds using Linear Algebra, Foundations and Trends® in Theoretical Computer Science, v.4 n.1–2, p.1-155, January 2009
	Peter Bürgisser , Martin Lotz, Lower bounds on the bounded coefficient complexity of bilinear maps, Journal of the ACM (JACM), v.51 n.3, p.464-482, May 2004
	Ran Raz, On the complexity of matrix product, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, 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