Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version)
BRICS Report Series
View Archive InfoField | Value | |
Title |
Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version)
|
|
Creator |
Nisan, Noam
Wigderson, Avi |
|
Description |
In this paper we describe a new technique for obtaining lower bounds onrestricted 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.
|
|
Publisher |
Aarhus University
|
|
Contributor |
—
|
|
Date |
1995-06-13
|
|
Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
Format |
application/pdf
|
|
Identifier |
https://tidsskrift.dk/brics/article/view/19944
10.7146/brics.v2i43.19944 |
|
Source |
BRICS Report Series; No 43 (1995): RS-43 Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version)
BRICS Report Series; No 43 (1995): RS-43 Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version) 1601-5355 0909-0878 |
|
Language |
eng
|
|
Relation |
https://tidsskrift.dk/brics/article/view/19944/17597
|
|
Rights |
Copyright (c) 2015 BRICS Report Series
|
|