Lower bounds on arithmetic circuits via partial derivatives

F
FOCS
1995
36th Annual Symposium on Foundations of Computer Science (FOCS'95)
Abstract - Lower bounds on arithmetic circuits via partial derivatives

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by N. Nisan Articles by A. Wigderson

36th Annual Symposium on Foundations of Computer Science (FOCS'95)

Milwaukee, Wisconsin

October 23-October 25

ISBN: 0-8186-7183-1

	ASCII Text	x
	N. Nisan, A. Wigderson, "Lower bounds on arithmetic circuits via partial derivatives," Foundations of Computer Science, IEEE Annual Symposium on, pp. 16, 36th Annual Symposium on Foundations of Computer Science (FOCS'95), 1995.

	BibTex	x
	@article{ 10.1109/SFCS.1995.492458, author = {N. Nisan and A. Wigderson}, title = {Lower bounds on arithmetic circuits via partial derivatives}, journal ={Foundations of Computer Science, IEEE Annual Symposium on}, volume = {0}, year = {1995}, issn = {0272-5428}, pages = {16}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1995.492458}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, IEEE Annual Symposium on TI - Lower bounds on arithmetic circuits via partial derivatives SN - 0272-5428 SP EP A1 - N. Nisan, A1 - A. Wigderson, PY - 1995 KW - computational complexity; polynomials; logic circuits; digital arithmetic; minimisation of switching nets; arithmetic circuits; partial derivatives; lower bounds; restricted classes; complexity measure; multivariate polynomials VL - 0 JA - Foundations of Computer Science, IEEE Annual Symposium on ER -

N. Nisan, Inst. of Comput. Sci., Hebrew Univ., Jerusalem, Israel

A. Wigderson, Inst. of Comput. Sci., Hebrew Univ., Jerusalem, Israel

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.1995.492458

We describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials and iterated matrix products.

Index Terms:

computational complexity; polynomials; logic circuits; digital arithmetic; minimisation of switching nets; arithmetic circuits; partial derivatives; lower bounds; restricted classes; complexity measure; multivariate polynomials

Citation:

N. Nisan, A. Wigderson, "Lower bounds on arithmetic circuits via partial derivatives," focs, pp.16, 36th Annual Symposium on Foundations of Computer Science (FOCS'95), 1995

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.