On the public citation graph

Lower bounds for arithmetic networks

https://doi.org/10.1007/bf01270397
0 signed · 67 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-07854-1_185openalex-snapshot
A lower bound of 1/2n2 on linear search programs for the knapsack problem
inferredcites →https://doi.org/10.1007/3-540-54233-7_163openalex-snapshot
Two P-complete problems in the theory of the reals
inferredcites →https://doi.org/10.1007/978-1-4612-0441-1_23openalex-snapshot
The non-scalar Model of Complexity in Computational Geometry
inferredcites →https://doi.org/10.1007/bf02104745openalex-snapshot
Lower bounds in algebraic computational complexity
inferredcites →https://doi.org/10.1007/bfb0016236openalex-snapshot
Parallel arithmetic computations: A survey
inferredcites →https://doi.org/10.1007/bfb0028969openalex-snapshot
On genuinely time bounded computations
inferredcites →https://doi.org/10.1016/0022-0000(79)90054-0openalex-snapshot
On the complexity of computations under varying sets of primitives
inferredcites →https://doi.org/10.1016/0304-3975(83)90002-6openalex-snapshot
Definability and fast quantifier elimination in algebraically closed fields
inferredcites →https://doi.org/10.1016/0885-064x(87)90021-5openalex-snapshot
On the topology of algorithms, I
inferredcites →https://doi.org/10.1016/b978-0-444-88071-0.50016-3openalex-snapshot
Algebraic Complexity Theory
inferredcites →https://doi.org/10.1016/s0022-0000(72)80034-5openalex-snapshot
Proving simultaneous positivity of linear forms
inferredcites →https://doi.org/10.1016/s0747-7171(88)80004-xopenalex-snapshot
Real quantifier elimination is doubly exponential
inferredcites →https://doi.org/10.1016/s0747-7171(88)80006-3openalex-snapshot
Complexity of deciding Tarski algebra
inferredcites →https://doi.org/10.1090/s0002-9939-1964-0161339-9openalex-snapshot
On the Betti Numbers of Real Varieties
inferredcites →https://doi.org/10.1090/s0273-0979-1989-15750-9openalex-snapshot
On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
inferredcites →https://doi.org/10.1142/s0218196792000244openalex-snapshot
TIME BOUNDED COMPUTATIONS OVER THE REALS
inferredcites →https://doi.org/10.1145/321941.321945openalex-snapshot
New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
inferredcites →https://doi.org/10.1145/321958.321973openalex-snapshot
Restructuring of Arithmetic Expressions For Parallel Evaluation
inferredcites →https://doi.org/10.1145/800061.808735openalex-snapshot
Lower bounds for algebraic computation trees
inferredcites →https://doi.org/10.1145/828.322450openalex-snapshot
A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
inferredcites →https://doi.org/10.1146/annurev.cs.03.060188.001533openalex-snapshot
Algebraic Complexity Theory
inferredcites →https://doi.org/10.24033/bsmf.2138openalex-snapshot
Sur la complexité du principe de Tarski-Seidenberg

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/jcom.1997.0436openalex-snapshot
Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations
inferred← citeshttps://doi.org/10.1006/jcom.1998.0472openalex-snapshot
On the Parallel Complexity of the Polynomial Ideal Membership Problem
inferred← citeshttps://doi.org/10.1006/jcom.1999.0519openalex-snapshot
Complexity Lower Bounds for Approximation Algebraic Computation Trees
inferred← citeshttps://doi.org/10.1006/jcom.1999.0526openalex-snapshot
Time-Space Tradeoffs in Algebraic Complexity Theory
inferred← citeshttps://doi.org/10.1006/jcom.2000.0572openalex-snapshot
Kronecker's and Newton's Approaches to Solving: A First Comparison
inferred← citeshttps://doi.org/10.1006/jcss.1997.1480openalex-snapshot
On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-In
inferred← citeshttps://doi.org/10.1006/jcss.1997.1495openalex-snapshot
Decision Tree Complexity and Betti Numbers
inferred← citeshttps://doi.org/10.1007/11549345_9openalex-snapshot
On the Number of Random Digits Required in MonteCarlo Integration of Definable Functions
inferred← citeshttps://doi.org/10.1007/3-540-44929-9_22openalex-snapshot
On the Complexity of Integer Programming in the Blum-Shub-Smale Computational Model
inferred← citeshttps://doi.org/10.1007/3-540-60114-7_16openalex-snapshot
When polynomial equation systems can be “solved” fast?
inferred← citeshttps://doi.org/10.1007/3-540-60114-7_4openalex-snapshot
How lower and upper complexity bounds meet in elimination theory
inferred← citeshttps://doi.org/10.1007/978-3-0348-9104-2_11openalex-snapshot
A computational method for diophantine approximation
inferred← citeshttps://doi.org/10.1007/978-3-540-69733-6_7openalex-snapshot
VC Dimension Bounds for Analytic Algebraic Computations
inferred← citeshttps://doi.org/10.1007/978-3-540-75225-7_12openalex-snapshot
Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations
inferred← citeshttps://doi.org/10.1007/978-3-540-75271-4_20openalex-snapshot
Finiteness Properties of Some Families of GP-Trees
inferred← citeshttps://doi.org/10.1007/bf01613615openalex-snapshot
Lower bounds for arithmetic networks II: Sum of Betti numbers
inferred← citeshttps://doi.org/10.1007/pl00009425openalex-snapshot
Randomized Complexity Lower Bound for Arrangements and Polyhedra
inferred← citeshttps://doi.org/10.1007/s00037-016-0145-8openalex-snapshot
Topological lower bounds for arithmetic networks
inferred← citeshttps://doi.org/10.1007/s000370050002openalex-snapshot
Complexity lower bounds for randomized computation trees over zero characteristic fields
inferred← citeshttps://doi.org/10.1007/s00200-006-0019-4openalex-snapshot
The big Mother of all dualities 2: Macaulay bases
inferred← citeshttps://doi.org/10.1007/s00454-017-9944-1openalex-snapshot
Multi-degree Bounds on the Betti Numbers of Real Varieties and Semi-algebraic Sets and Applications
inferred← citeshttps://doi.org/10.1007/s10208-002-0065-7openalex-snapshot
The Hardness of Polynomial Equation Solving
inferred← citeshttps://doi.org/10.1007/s10208-014-9222-zopenalex-snapshot
A Complexity Theory of Constructible Functions and Sheaves
inferred← citeshttps://doi.org/10.1007/s10472-009-9148-3openalex-snapshot
On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations
inferred← citeshttps://doi.org/10.1016/0020-0190(96)00120-2openalex-snapshot
A size-depth trade-off for the analog computation of Boolean functions
inferred← citeshttps://doi.org/10.1016/0022-4049(95)00105-0openalex-snapshot
Semi-algebraic decision complexity, the real spectrum, and degree
inferred← citeshttps://doi.org/10.1016/0304-3975(96)00002-3openalex-snapshot
Generalized Knapsack problems and fixed degree separations
inferred← citeshttps://doi.org/10.1016/j.aim.2016.09.015openalex-snapshot
Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
inferred← citeshttps://doi.org/10.1016/j.jco.2008.07.002openalex-snapshot
Some lower bounds for the complexity of the linear programming feasibility problem over the reals
inferred← citeshttps://doi.org/10.1016/s0022-4049(96)00099-0openalex-snapshot
Straight-line programs in geometric elimination theory
inferred← citeshttps://doi.org/10.1016/s0022-4049(97)00015-7openalex-snapshot
Lower bounds for diophantine approximations
inferred← citeshttps://doi.org/10.1016/s0022-4049(98)00148-0openalex-snapshot
On the intrinsic complexity of the arithmetic Nullstellensatz
inferred← citeshttps://doi.org/10.1016/s0885-064x(02)00028-6openalex-snapshot
Systems of rational polynomial equations have polynomial size approximate zeros on the average
inferred← citeshttps://doi.org/10.1016/s0893-9659(01)00116-1openalex-snapshot
An alternative to Ben-Or's lower bound for the knapsack problem complexity
inferred← citeshttps://doi.org/10.1109/ictai.2008.14openalex-snapshot
Straight Line Programs: A New Linear Genetic Programming Approach
inferred← citeshttps://doi.org/10.1111/j.1600-0471.1994.tb00059.xopenalex-snapshot
London‐Bahrain Archaeological Expedition: 1991–2 excavations at Saar
inferred← citeshttps://doi.org/10.1112/plms/pdv059openalex-snapshot
On a real analog of Bezout inequality and the number of connected components of sign conditions
inferred← citeshttps://doi.org/10.1112/s0024610703004939openalex-snapshot
BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS
inferred← citeshttps://doi.org/10.1142/s0218213009000391openalex-snapshot
A NEW LINEAR GENETIC PROGRAMMING APPROACH BASED ON STRAIGHT LINE PROGRAMS: SOME THEORETICAL AND EXPERIMENTAL ASPECTS
inferred← citeshttps://doi.org/10.1145/276698.276745openalex-snapshot
Randomized complexity lower bounds
inferred← citeshttps://doi.org/10.1145/3717823.3718198openalex-snapshot
Polynomial-Time PIT from (Almost) Necessary Assumptions
inferred← citeshttps://doi.org/10.36045/bbms/1105730626openalex-snapshot
A survey on real structural complexity theory
inferred← citeshttps://doi.org/10.48550/arxiv.1510.03387openalex-snapshot
Topological lower bounds for arithmetic networks
inferred← citeshttps://doi.org/10.48550/arxiv.alg-geom/9608010openalex-snapshot
Lower Bounds for diophantine Approximation
inferred← citeshttps://doi.org/10.48550/arxiv.alg-geom/9609003openalex-snapshot
Polar Varieties and Efficient Real Equation Solving: The Hypersurface Case
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.