Lower bounds for arithmetic networks
DOI10.1007/BF01270397zbMATH Open0769.68055OpenAlexW1993735243MaRDI QIDQ1803554FDOQ1803554
J. L. Montaña, Luis Miguel Pardo
Publication date: 29 June 1993
Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01270397
Recommendations
algebraic complexity theorydegreeconnected componentsquantifier eliminationsemialgebraic setsparallel complexityKnapsack problemlower bounds for depth of arithmetic networksparallel time
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Decidability and field theory (12L05)
Cites Work
- Title not available (Why is that?)
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On the Betti Numbers of Real Varieties
- Proving simultaneous positivity of linear forms
- Title not available (Why is that?)
- Lower bounds in algebraic computational complexity
- Title not available (Why is that?)
- Definability and fast quantifier elimination in algebraically closed fields
- On the topology of algorithms. I
- Real quantifier elimination is doubly exponential
- Complexity of deciding Tarski algebra
- Title not available (Why is that?)
- New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
- A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
- Maximal bilinear complexity and codes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- TIME BOUNDED COMPUTATIONS OVER THE REALS
Cited In (22)
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- An alternative to Ben-Or's lower bound for the knapsack problem complexity
- On the parallel complexity of the polynomial ideal membership problem
- Lower bounds for diophantine approximations
- Some lower bounds for the complexity of the linear programming feasibility problem over the reals
- Title not available (Why is that?)
- Straight-line programs in geometric elimination theory
- Kronecker's and Newton's approaches to solving: a first comparison
- On defining integers and proving arithmetic circuit lower bounds
- Semi-algebraic decision complexity, the real spectrum, and degree
- On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations
- Generalized Knapsack problems and fixed degree separations
- Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations
- On a real analog of Bézout inequality and the number of connected components of sign conditions
- Decision tree complexity and Betti numbers
- Topological lower bounds for arithmetic networks
- Nearly sharp complexity bounds for multiprocessor algebraic computations
- Complexity lower bounds for approximation algebraic computation trees
- A size-depth trade-off for the analog computation of Boolean functions
- Time-space tradeoffs in algebraic complexity theory
- Lower bounds for arithmetic networks. II: Sum of Betti numbers
- On the computation of Boolean functions by analog circuits of bounded fan-in
This page was built for publication: Lower bounds for arithmetic networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803554)
