Lower bounds on arithmetic circuits via partial derivatives

DOI10.1007/BF01294256zbMATH Open0890.68074OpenAlexW2171403864MaRDI QIDQ1377574FDOQ1377574

Authors: Noam Nisan, A. Wigderson 

Publication date: 11 June 1998

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01294256

Recommendations

• Depth-3 arithmetic circuits over fields of characteristic zero
• Arithmetic circuit lower bounds via maximum-rank of partial derivative matrices
• On the complexity of partial derivatives
• Lower bounds on monotone arithmetic circuits with restricted depths

zbMATH Keywords

arithmetic circuitscircuit complexitycomplexity measure for multivariate polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Negation can be exponentially powerful
• Fast Parallel Computation of Polynomials Using Few Processors
• A direct version of Shamir and Snir's lower bounds on monotone circuit depth
• On the depth complexity of formulas
• A Certain Class of Incidence Matrices

Cited In (65)

• Multi-\(k\)-ic depth three circuit lower bound
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polystability in positive characteristic and degree lower bounds for invariant rings
• Title not available (Why is that?)
• Resource trade-offs in syntactically multilinear arithmetic circuits
• A Selection of Lower Bounds for Arithmetic Circuits
• Affine projections of symmetric polynomials.
• Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
• Obtaining lower bounds using artificial components
• On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• Barriers for Rank Methods in Arithmetic Complexity
• Circuits in bounded arithmetic. I
• Title not available (Why is that?)
• Interval conjectures for level Hilbert functions
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
• On Lower Bounds for Constant Width Arithmetic Circuits
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Subexponential size hitting sets for bounded depth multilinear formulas
• Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications
• The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
• Approaching the Chasm at Depth Four
• On the Expressive Power of Read-Once Determinants
• On defining integers and proving arithmetic circuit lower bounds
• A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas
• Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• Unifying known lower bounds via geometric complexity theory
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Homogeneous formulas and symmetric polynomials
• Improved bounds on the an-complexity of \(O(1)\)-linear functions
• A note on parameterized polynomial identity testing using hitting set generators
• Non-commutative circuits and the sum-of-squares problem
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• Formulas versus Circuits for Small Distance Connectivity
• Lower bounds for arithmetic circuits via the Hankel matrix
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• Partial derivatives of a generic subspace of a vector space of forms: Quotients of level algebras of arbitrary type
• Lower bounds for the determinantal complexity of explicit low degree polynomials
• Deterministic polynomial identity testing in non-commutative models
• The method of shifted partial derivatives cannot separate the permanent from the determinant
• A quadratic lower bound for algebraic branching programs
• Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
• Geometric complexity theory: an introduction for geometers
• On the limits of depth reduction at depth 3 over small finite fields
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Title not available (Why is that?)
• On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
• Lower bounds for special cases of syntactic multilinear ABPs
• Lower bounds for the complexity of polynomials
• Quadratic lower bounds for algebraic branching programs and formulas
• Uniform derandomization from pathetic lower bounds
• Arithmetic circuits: a chasm at depth 3
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• Title not available (Why is that?)
• A super-quadratic lower bound for depth four arithmetic circuits
• On the Symmetries of and Equivalence Test for Design Polynomials.
• The Computational Power of Depth Five Arithmetic Circuits
• Lower bounds for the sum of small-size algebraic branching programs
• Notes on Boolean read-\(k\) and multilinear circuits
• Schur polynomials do not have small formulas if the determinant does not

This page was built for publication: Lower bounds on arithmetic circuits via partial derivatives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377574)