On the public citation graph
Lower bounds in algebraic computational complexity
0 signed · 63 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.1002/cpa.3160230204openalex-snapshot
On the number of multiplications necessary to compute certain functions
inferredcites →https://doi.org/10.1007/3-540-08353-7_135openalex-snapshot
Graph-theoretic arguments in low-level complexity
inferredcites →https://doi.org/10.1007/3-540-09118-1_30openalex-snapshot
On the additive complexity of polynomials and some new lower bounds
inferredcites →https://doi.org/10.1007/3-540-10856-4_94openalex-snapshot
Multiplicative complexity of a bilinear form over a commutative ring
inferredcites →https://doi.org/10.1007/bf01404101openalex-snapshot
A lower bound for the computational complexity of a set of disjunctives in a monotone basis
inferredcites →https://doi.org/10.1007/bf01436566openalex-snapshot
Die Berechnungskomplexit�t von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
inferredcites →https://doi.org/10.1007/bf01465456openalex-snapshot
Relation between rank and multiplicative complexity of a bilinear form over a commutative Noetherian ring
inferredcites →https://doi.org/10.1007/bf01693976openalex-snapshot
Application of separability and independence notions for proving lower bounds of circuit complexity
inferredcites →https://doi.org/10.1016/0022-0000(80)90056-2openalex-snapshot
Time-space tradeoffs for computing functions, using connectivity properties of their circuits
inferredcites →https://doi.org/10.1016/0304-3975(76)90083-9openalex-snapshot
A lower bound on the number of additions in monotone computations
inferredcites →https://doi.org/10.1016/0304-3975(80)90019-5openalex-snapshot
Lower bounds for polynomials with algebraic coefficients
inferredcites →https://doi.org/10.1016/0304-3975(80)90060-2openalex-snapshot
Negation can be exponentially powerful
inferredcites →https://doi.org/10.1016/0304-3975(80)90068-7openalex-snapshot
On the additive complexity of polynomials
inferredcites →https://doi.org/10.1016/0304-3975(81)90070-0openalex-snapshot
On the algorithmic complexity of associative algebras
inferredcites →https://doi.org/10.1016/0304-3975(82)90014-7openalex-snapshot
Additive complexity in directed computations
inferredcites →https://doi.org/10.1070/rm1966v021n01abeh004147openalex-snapshot
METHODS OF COMPUTING VALUES OF POLYNOMIALS
inferredcites →https://doi.org/10.1109/tc.1980.1675583openalex-snapshot
An Improved Lower Bound on Polynomial Multiplication
inferredcites →https://doi.org/10.1109/tit.1978.1055938openalex-snapshot
Space-time trade-offs on the FFT algorithm
inferredcites →https://doi.org/10.1137/0202007openalex-snapshot
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
inferredcites →https://doi.org/10.1137/0203010openalex-snapshot
Polynomials with Rational Coefficients Which are Hard to Compute
inferredcites →https://doi.org/10.1137/0203011openalex-snapshot
An Algorithm for the Computation of Linear Forms
inferredcites →https://doi.org/10.1137/0205013openalex-snapshot
On the Number of Additions to Compute Specific Polynomials
inferredcites →https://doi.org/10.1137/0205027openalex-snapshot
Computational Complexity over Finite Fields
inferredcites →https://doi.org/10.1137/0208037openalex-snapshot
Optimal Evaluation of Pairs of Bilinear Forms
inferredcites →https://doi.org/10.1137/0210032openalex-snapshot
Partial and Total Matrix Multiplication
inferredcites →https://doi.org/10.1137/0211038openalex-snapshot
On the Asymptotic Complexity of Matrix Multiplication
inferredcites →https://doi.org/10.1137/0212001openalex-snapshot
The Computational Complexity of Continued Fractions
inferredcites →https://doi.org/10.1145/2402.2403openalex-snapshot
Time-Space trade-offs for some algebraic problems
inferredcites →https://doi.org/10.1145/321752.321761openalex-snapshot
Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
inferredcites →https://doi.org/10.1145/322003.322014openalex-snapshot
Algebras Having Linear Multiplicative Complexities
inferredcites →https://doi.org/10.1145/800116.803752openalex-snapshot
On non-linear lower bounds in computational complexity
inferredcites →https://doi.org/10.1145/800133.804344openalex-snapshot
Computational complexity of computing polynomials over the fields of real and complex numbers
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-1-4612-0441-1_23openalex-snapshot
The non-scalar Model of Complexity in Computational Geometry
inferred← citeshttps://doi.org/10.1007/bf01270397openalex-snapshot
Lower bounds for arithmetic networks
inferred← citeshttps://doi.org/10.1007/s10208-014-9190-3openalex-snapshot
Tensor Rank: Matching Polynomials and Schur Rings
inferred← citeshttps://doi.org/10.1007/s10208-014-9231-yopenalex-snapshot
Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees
inferred← citeshttps://doi.org/10.1016/0024-3795(95)00453-xopenalex-snapshot
Matrix Bruhat decompositions with a remark on the QR (GR) algorithm
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00177-8openalex-snapshot
Computability of the additive complexity of algebraic circuits with root extracting
inferred← citeshttps://doi.org/10.1016/s0020-0190(98)00089-1openalex-snapshot
On Kolmogorov complexity in the real Turing machine setting
inferred← citeshttps://doi.org/10.1017/9781108671644.016openalex-snapshot
Extension Complexity of Polytopes
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.1109/sfcs.1998.743456openalex-snapshot
Exponential complexity lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields
inferred← citeshttps://doi.org/10.1137/s0097539793258313openalex-snapshot
Computing the Additive Complexity of Algebraic Circuits with Root Extracting
inferred← citeshttps://doi.org/10.1307/mmj/1441116656openalex-snapshot
Integer complexity and well-ordering
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.