Lower bounds on arithmetic circuits via partial derivatives

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

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

Cites work

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

Cited in

(68)

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

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)