Record Details

Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version)

BRICS Report Series

View Archive Info
 
 
Field 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