Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version)
AbstractIn this paper 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.
How to Cite
Nisan, N., & Wigderson, A. (1995). Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version). BRICS Report Series, 2(43). https://doi.org/10.7146/brics.v2i43.19944
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.