Lower bounds on arithmetic circuits via partial derivatives
From MaRDI portal
Publication:1377574
DOI10.1007/BF01294256zbMath0890.68074OpenAlexW2171403864MaRDI QIDQ1377574
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
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (55)
Affine projections of symmetric polynomials. ⋮ Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ Interval conjectures for level Hilbert functions ⋮ Improved bounds on the an-complexity of \(O(1)\)-linear functions ⋮ Quadratic lower bounds for algebraic branching programs and formulas ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ On the limits of depth reduction at depth 3 over small finite fields ⋮ Uniform derandomization from pathetic lower bounds ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ On the Expressive Power of Read-Once Determinants ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Schur polynomials do not have small formulas if the determinant does not ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Lower bounds for the determinantal complexity of explicit low degree polynomials ⋮ Homogeneous formulas and symmetric polynomials ⋮ Unnamed Item ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ The method of shifted partial derivatives cannot separate the permanent from the determinant ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ A note on parameterized polynomial identity testing using hitting set generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree ⋮ Unnamed Item ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Lower bounds for arithmetic circuits via the Hankel matrix ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials ⋮ A quadratic lower bound for algebraic branching programs ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Unnamed Item ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees ⋮ Approaching the Chasm at Depth Four ⋮ Partial derivatives of a generic subspace of a vector space of forms: Quotients of level algebras of arbitrary type ⋮ Polystability in positive characteristic and degree lower bounds for invariant rings ⋮ Geometric complexity theory: an introduction for geometers ⋮ Unifying known lower bounds via geometric complexity theory
Cites Work
This page was built for publication: Lower bounds on arithmetic circuits via partial derivatives
