Lower bounds for arithmetic networks

DOI10.1007/BF01270397zbMath0769.68055OpenAlexW1993735243MaRDI QIDQ1803554

José Luis 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

zbMATH Keywords

connected componentsquantifier eliminationdegreeparallel complexityKnapsack problemsemialgebraic setsalgebraic complexity theorylower bounds for depth of arithmetic networksparallel time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Decidability and field theory (12L05)

Related Items

On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations, Generalized Knapsack problems and fixed degree separations, Lower bounds for diophantine approximations, Nearly sharp complexity bounds for multiprocessor algebraic computations, Lower bounds for arithmetic networks. II: Sum of Betti numbers, Semi-algebraic decision complexity, the real spectrum, and degree, Straight-line programs in geometric elimination theory, Topological lower bounds for arithmetic networks, Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations, Time-space tradeoffs in algebraic complexity theory, A size-depth trade-off for the analog computation of Boolean functions, On the computation of Boolean functions by analog circuits of bounded fan-in, Kronecker's and Newton's approaches to solving: a first comparison, Decision tree complexity and Betti numbers, On a real analog of Bezout inequality and the number of connected components of sign conditions, Some lower bounds for the complexity of the linear programming feasibility problem over the reals, On the parallel complexity of the polynomial ideal membership problem, Complexity lower bounds for approximation algebraic computation trees, An alternative to Ben-Or's lower bound for the knapsack problem complexity, Systems of rational polynomial equations have polynomial size approximate zeros on the average

Cites Work

• Definability and fast quantifier elimination in algebraically closed fields
• Lower bounds in algebraic computational complexity
• On the topology of algorithms. I
• Real quantifier elimination is doubly exponential
• Complexity of deciding Tarski algebra
• Proving simultaneous positivity of linear forms
• Maximal bilinear complexity and codes
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• TIME BOUNDED COMPUTATIONS OVER THE REALS
• New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Betti Numbers of Real Varieties
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item