On the public citation graph
Lower bounds on arithmetic circuits via partial derivatives
0 signed · 153 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/bf01744302openalex-snapshot
On the depth complexity of formulas
inferredcites →https://doi.org/10.1016/0020-0190(94)90061-2openalex-snapshot
A direct version of Shamir and Snir's lower bounds on monotone circuit depth
inferredcites →https://doi.org/10.1016/0304-3975(80)90018-3openalex-snapshot
On the average number of rebalancing operations in weight-balanced trees
inferredcites →https://doi.org/10.1016/0304-3975(80)90060-2openalex-snapshot
Negation can be exponentially powerful
inferredcites →https://doi.org/10.1090/s0002-9939-1966-0204305-9openalex-snapshot
A Certain Class of Incidence Matrices
inferredcites →https://doi.org/10.1109/fscs.1990.89584openalex-snapshot
On interpolation by analytic functions with special properties and some weak lower bounds on the size of circuits with symmetric gates
inferredcites →https://doi.org/10.1137/0212043openalex-snapshot
Fast Parallel Computation of Polynomials Using Few Processors
inferredcites →https://doi.org/10.1145/103418.103462openalex-snapshot
Lower bounds for non-commutative computation
inferredcites →https://doi.org/10.1146/annurev.cs.03.060188.001533openalex-snapshot
Algebraic Complexity Theory
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/11537311_4openalex-snapshot
On the Incompressibility of Monotone DNFs
inferred← citeshttps://doi.org/10.1007/3-540-44450-5_14openalex-snapshot
Depth-3 Arithmetic Circuits for S innsu2 (X) and Extensions of the Graham-Pollack Theorem
inferred← citeshttps://doi.org/10.1007/978-3-030-43662-9_6openalex-snapshot
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
inferred← citeshttps://doi.org/10.1007/978-3-319-05446-9_5openalex-snapshot
A Selection of Lower Bounds for Arithmetic Circuits
inferred← citeshttps://doi.org/10.1007/978-3-319-22177-9_8openalex-snapshot
On the Expressive Power of Read-Once Determinants
inferred← citeshttps://doi.org/10.1007/978-3-319-32162-2_1openalex-snapshot
$$P\mathop{ =}\limits^{?}NP$$
inferred← citeshttps://doi.org/10.1007/978-3-540-30538-5_38openalex-snapshot
Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching Require Exponential Size
inferred← citeshttps://doi.org/10.1007/978-3-540-45167-9_34openalex-snapshot
Learning Arithmetic Circuits via Partial Derivatives
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_6openalex-snapshot
Diagonal Circuit Identity Testing and Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-540-73545-8_46openalex-snapshot
“Resistant” Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas
inferred← citeshttps://doi.org/10.1007/978-3-642-03351-3_17openalex-snapshot
Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_29openalex-snapshot
Uniform Derandomization from Pathetic Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-662-44465-8_16openalex-snapshot
On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_27openalex-snapshot
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
inferred← citeshttps://doi.org/10.1007/978-981-92-3309-0_27openalex-snapshot
On the Arithmetic Complexity of Euler Tours
inferred← citeshttps://doi.org/10.1007/978-981-97-2340-9_30openalex-snapshot
Lower Bounds for the Sum of Small-Size Algebraic Branching Programs
inferred← citeshttps://doi.org/10.1007/s00037-008-0254-0openalex-snapshot
Balancing Syntactically Multilinear Arithmetic Circuits
inferred← citeshttps://doi.org/10.1007/s00037-009-0270-8openalex-snapshot
Lower Bounds and Separations for Constant Depth Multilinear Circuits
inferred← citeshttps://doi.org/10.1007/s00037-011-0007-3openalex-snapshot
Homogeneous Formulas and Symmetric Polynomials
inferred← citeshttps://doi.org/10.1007/s00037-013-0072-xopenalex-snapshot
Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits
inferred← citeshttps://doi.org/10.1007/s00037-015-0097-4openalex-snapshot
Deterministic polynomial identity tests for multilinear bounded-read formulae
inferred← citeshttps://doi.org/10.1007/s00037-015-0103-xopenalex-snapshot
Unifying Known Lower Bounds via Geometric Complexity Theory
inferred← citeshttps://doi.org/10.1007/s00037-016-0131-1openalex-snapshot
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
inferred← citeshttps://doi.org/10.1007/s00037-016-0132-0openalex-snapshot
Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin
inferred← citeshttps://doi.org/10.1007/s00037-021-00214-1openalex-snapshot
Lower Bounds for Arithmetic Circuits via the Hankel Matrix
inferred← citeshttps://doi.org/10.1007/s00037-022-00223-8openalex-snapshot
Quadratic Lower Bounds for Algebraic Branching Programs and Formulas
inferred← citeshttps://doi.org/10.1007/s00037-022-00224-7openalex-snapshot
Improved bounds on the AN-complexity of $$O(1)$$-linear functions
inferred← citeshttps://doi.org/10.1007/s00037-023-00236-xopenalex-snapshot
Schur Polynomials Do Not Have Small Formulas If the Determinant does not
inferred← citeshttps://doi.org/10.1007/s00037-025-00283-6openalex-snapshot
Towards Optimal Depth-Reductions for Algebraic Formulas
inferred← citeshttps://doi.org/10.1007/s00209-009-0507-xopenalex-snapshot
Simplicial complexes and Macaulay’s inverse systems
inferred← citeshttps://doi.org/10.1007/s00224-007-2013-zopenalex-snapshot
On the Incompressibility of Monotone DNFs
inferred← citeshttps://doi.org/10.1007/s00224-010-9308-1openalex-snapshot
Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
inferred← citeshttps://doi.org/10.1007/s00224-016-9742-9openalex-snapshot
Multi-k-ic Depth Three Circuit Lower Bound
inferred← citeshttps://doi.org/10.1007/s00493-019-4009-0openalex-snapshot
Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
inferred← citeshttps://doi.org/10.1007/s11565-014-0202-7openalex-snapshot
Geometric complexity theory: an introduction for geometers
inferred← citeshttps://doi.org/10.1016/j.dam.2024.09.023openalex-snapshot
Notes on Boolean read- k and multilinear circuits
inferred← citeshttps://doi.org/10.1016/j.ic.2017.04.007openalex-snapshot
On the limits of depth reduction at depth 3 over small finite fields
inferred← citeshttps://doi.org/10.1016/j.ipl.2019.105839openalex-snapshot
A note on parameterized polynomial identity testing using hitting set generators
inferred← citeshttps://doi.org/10.1016/j.ipl.2019.105900openalex-snapshot
Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
inferred← citeshttps://doi.org/10.1016/j.jalgebra.2007.09.030openalex-snapshot
Interval conjectures for level Hilbert functions
inferred← citeshttps://doi.org/10.1016/j.jcss.2010.06.013openalex-snapshot
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.10.047openalex-snapshot
Lower bounds for special cases of syntactic multilinear ABPs
inferred← citeshttps://doi.org/10.1016/j.tcs.2025.115214openalex-snapshot
Lower bounds for the sum of small-size algebraic branching programs
inferred← citeshttps://doi.org/10.1016/s0022-0000(02)00021-1openalex-snapshot
Affine projections of symmetric polynomials
inferred← citeshttps://doi.org/10.1070/sm2012v203n10abeh004270openalex-snapshot
A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
inferred← citeshttps://doi.org/10.1090/s0002-9947-07-04015-9openalex-snapshot
Partial derivatives of a generic subspace of a vector space of forms: Quotients of level algebras of arbitrary type
inferred← citeshttps://doi.org/10.1090/s0894-0347-2011-00694-2openalex-snapshot
Non-commutative circuits and the sum-of-squares problem
inferred← citeshttps://doi.org/10.1098/rsta.2011.0318openalex-snapshot
Uniform derandomization from pathetic lower bounds
inferred← citeshttps://doi.org/10.1109/ccc.1999.766267openalex-snapshot
Depth-3 arithmetic formulae over fields of characteristic zero
inferred← citeshttps://doi.org/10.1109/ccc.2001.933883openalex-snapshot
Affine projections of symmetric polynomials
inferred← citeshttps://doi.org/10.1109/ccc.2004.11openalex-snapshot
Deterministic polynomial identity testing in non commutative models
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313845openalex-snapshot
Deterministic polynomial identity testing in non commutative models
inferred← citeshttps://doi.org/10.1109/ccc.2010.34openalex-snapshot
Relationless Completeness and Separations
inferred← citeshttps://doi.org/10.1109/ccc.2013.16openalex-snapshot
Approaching the Chasm at Depth Four
inferred← citeshttps://doi.org/10.1109/ccc.2014.23openalex-snapshot
Recent Progress on Lower Bounds for Arithmetic Circuits
inferred← citeshttps://doi.org/10.1109/ccc.2014.35openalex-snapshot
Unifying Known Lower Bounds via Geometric Complexity Theory
inferred← citeshttps://doi.org/10.1109/focs.2004.42openalex-snapshot
Multilinear- NC₁ ≠ Multilinear- NC₂
inferred← citeshttps://doi.org/10.1109/focs.2004.9openalex-snapshot
Algebras with Polynomial Identities and Computing the Determinant
inferred← citeshttps://doi.org/10.1109/focs.2008.32openalex-snapshot
Arithmetic Circuits: A Chasm at Depth Four
inferred← citeshttps://doi.org/10.1109/focs.2011.94openalex-snapshot
Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits
inferred← citeshttps://doi.org/10.1109/focs.2013.34openalex-snapshot
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs
inferred← citeshttps://doi.org/10.1109/focs.2013.68openalex-snapshot
Arithmetic Circuits: A Chasm at Depth Three
inferred← citeshttps://doi.org/10.1109/focs.2014.15openalex-snapshot
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
inferred← citeshttps://doi.org/10.1109/focs.2015.35openalex-snapshot
Deterministic Divisibility Testing via Shifted Partial Derivatives
inferred← citeshttps://doi.org/10.1109/focs.2019.00054openalex-snapshot
More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00087openalex-snapshot
Learning sums of powers of low-degree polynomials in the non-degenerate case
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00083openalex-snapshot
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00026openalex-snapshot
Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits
inferred← citeshttps://doi.org/10.1137/05063605xopenalex-snapshot
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
inferred← citeshttps://doi.org/10.1137/070707932openalex-snapshot
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch160openalex-snapshot
Smaller Low-Depth Circuits for Kronecker Powers
inferred← citeshttps://doi.org/10.1137/140957123openalex-snapshot
Arithmetic Circuits: A Chasm at Depth 3
inferred← citeshttps://doi.org/10.1137/140990280openalex-snapshot
Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
inferred← citeshttps://doi.org/10.1137/151002423openalex-snapshot
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
inferred← citeshttps://doi.org/10.1137/15m1027310openalex-snapshot
Formulas versus Circuits for Small Distance Connectivity
inferred← citeshttps://doi.org/10.1137/18m1173319openalex-snapshot
The Computational Power of Depth Five Arithmetic Circuits
inferred← citeshttps://doi.org/10.1137/18m1191567openalex-snapshot
Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications
inferred← citeshttps://doi.org/10.1137/21m1443339openalex-snapshot
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity
inferred← citeshttps://doi.org/10.1137/s009753970342465xopenalex-snapshot
Computing Elementary Symmetric Polynomials with a Subpolynomial Numberof Multiplications
inferred← citeshttps://doi.org/10.1137/s0097539705447359openalex-snapshot
Algebras with Polynomial Identities and Computing the Determinant
inferred← citeshttps://doi.org/10.1145/1007352.1007353openalex-snapshot
Multi-linear formulas for permanent and determinant are of super-polynomial size
inferred← citeshttps://doi.org/10.1145/1060590.1060678openalex-snapshot
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
inferred← citeshttps://doi.org/10.1145/1806689.1806780openalex-snapshot
Tensor-rank and lower bounds for arithmetic formulas
inferred← citeshttps://doi.org/10.1145/1806689.1806781openalex-snapshot
Non-commutative circuits and the sum-of-squares problem
inferred← citeshttps://doi.org/10.1145/2213977.2213995openalex-snapshot
On identity testing of tensors, low-rank recovery and compressed sensing
inferred← citeshttps://doi.org/10.1145/2213977.2214034openalex-snapshot
Separating multilinear branching programs and formulas
inferred← citeshttps://doi.org/10.1145/2213977.2214036openalex-snapshot
Affine projections of polynomials
inferred← citeshttps://doi.org/10.1145/2488608.2488649openalex-snapshot
Quasi-polynomial hitting-set for set-depth-Δ formulas
inferred← citeshttps://doi.org/10.1145/2535928openalex-snapshot
Tensor-Rank and Lower Bounds for Arithmetic Formulas
inferred← citeshttps://doi.org/10.1145/2591796.2591816openalex-snapshot
Hitting sets for multilinear read-once algebraic branching programs, in any order
inferred← citeshttps://doi.org/10.1145/2591796.2591823openalex-snapshot
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
inferred← citeshttps://doi.org/10.1145/2591796.2591824openalex-snapshot
Lower bounds for depth 4 formulas computing iterated matrix multiplication
inferred← citeshttps://doi.org/10.1145/2591796.2591828openalex-snapshot
Formulas vs. circuits for small distance connectivity
inferred← citeshttps://doi.org/10.1145/2591796.2591847openalex-snapshot
A super-polynomial lower bound for regular arithmetic formulas
inferred← citeshttps://doi.org/10.1145/2897518.2897550openalex-snapshot
On the size of homogeneous and of depth four formulas with low individual degree
inferred← citeshttps://doi.org/10.1145/3055399.3055496openalex-snapshot
Succinct hitting sets and barriers to proving algebraic circuits lower bounds
inferred← citeshttps://doi.org/10.1145/3065468openalex-snapshot
Technical Perspective: Low-depth arithmetic circuits
inferred← citeshttps://doi.org/10.1145/3065470openalex-snapshot
Unexpected power of low-depth arithmetic circuits
inferred← citeshttps://doi.org/10.1145/3188745.3188912openalex-snapshot
On the complexity of hazard-free circuits
inferred← citeshttps://doi.org/10.1145/3209663openalex-snapshot
On Algebraic Branching Programs of Small Width
inferred← citeshttps://doi.org/10.1145/3313232openalex-snapshot
Lower bounds for Sum and Sum of Products of Read-once Formulas
inferred← citeshttps://doi.org/10.1145/3313276.3316360openalex-snapshot
Reconstruction of non-degenerate homogeneous depth three circuits
inferred← citeshttps://doi.org/10.1145/3369928openalex-snapshot
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits
inferred← citeshttps://doi.org/10.1145/3371506openalex-snapshot
On the Power of Border of Depth-3 Arithmetic Circuits
inferred← citeshttps://doi.org/10.1145/3460952openalex-snapshot
On Computing Multilinear Polynomials Using Multi- r -ic Depth Four Circuits
inferred← citeshttps://doi.org/10.1145/3519935.3520044openalex-snapshot
Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication
inferred← citeshttps://doi.org/10.1145/3611094openalex-snapshot
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
inferred← citeshttps://doi.org/10.1145/3618260.3649760openalex-snapshot
On the Power of Homogeneous Algebraic Formulas
inferred← citeshttps://doi.org/10.1145/3665800openalex-snapshot
Hitting Sets for Orbits of Circuit Classes and Polynomial Families
inferred← citeshttps://doi.org/10.1145/3689957openalex-snapshot
Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits
inferred← citeshttps://doi.org/10.1561/0400000039openalex-snapshot
Arithmetic Circuits: A Survey of Recent Results and Open Questions
inferred← citeshttps://doi.org/10.1561/0400000043openalex-snapshot
Partial Derivatives in Arithmetic Complexity and Beyond
inferred← citeshttps://doi.org/10.1561/9781601984814openalex-snapshot
Partial Derivatives in Arithmetic Complexity and Beyond
inferred← citeshttps://doi.org/10.4171/jca/66openalex-snapshot
Polystability in positive characteristic and degree lower bounds for invariant rings
inferred← citeshttps://doi.org/10.4213/sm7904openalex-snapshot
Об одном методе получения нижних оценок сложности монотонных арифметических схем, вычисляющих действительные многочлены
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.32openalex-snapshot
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.33openalex-snapshot
Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2017.31openalex-snapshot
An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2020.14openalex-snapshot
Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't
inferred← citeshttps://doi.org/10.48550/arxiv.0712.1804openalex-snapshot
Simplicial complexes and Macaulay's inverse systems
inferred← citeshttps://doi.org/10.48550/arxiv.1309.5668openalex-snapshot
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
inferred← citeshttps://doi.org/10.48550/arxiv.1803.05933openalex-snapshot
Some Closure Results for Polynomial Factorization and Applications
inferred← citeshttps://doi.org/10.48550/arxiv.1911.11793openalex-snapshot
A Quadratic Lower Bound for Algebraic Branching Programs and Formulas
inferred← citeshttps://doi.org/10.48550/arxiv.2006.02374openalex-snapshot
On tensor rank and commuting matrices
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0110031openalex-snapshot
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem
inferred← citeshttps://doi.org/10.5555/2833227.2833235openalex-snapshot
Lower bounds for depth three arithmetic circuits with small bottom fanin
inferred← citeshttps://doi.org/10.70675/10b79942z0379z46a4zbb33z9331f6eae3dbopenalex-snapshot
Des fonctions difficiles en compilation de connaissances : bornes inférieures et applications
inferred← citeshttps://doi.org/10.70675/9c6c6a19z65bdz4aa2zbb8bz8326795242dbopenalex-snapshot
Lower bounds and reconstruction algorithms for sums of affine powers
inferred← citeshttps://doi.org/10.7282/t35d8qvqopenalex-snapshot
On circuit complexity classes and iterated matrix multiplication
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.