Nearly sharp complexity bounds for multiprocessor algebraic computations

DOI10.1006/jcom.1997.0436zbMath0872.68053OpenAlexW1969540178MaRDI QIDQ1361876

Dima Yu. Grigoriev

Publication date: 13 October 1997

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/7888ac3fe4a3a4fd45a26ba6a08113bc0f96895c

zbMATH Keywords

multiprocessor algebraic computation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Complexity lower bounds for approximation algebraic computation trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Point location in arrangements of hyperplanes
• Complexity of deciding Tarski algebra
• Lower bounds for arithmetic networks
• Simulating probabilistic by deterministic algebraic computation trees
• Lower bounds for arithmetic networks. II: Sum of Betti numbers
• Lower bounds for parallel linear programming and other problems
• On the Polyhedral Decision Problem
• Lower bounds for algebraic decision trees
• On the Power of Real Turing Machines over Binary Inputs
• On the Betti Numbers of Real Varieties
• Decision tree complexity and Betti numbers

This page was built for publication: Nearly sharp complexity bounds for multiprocessor algebraic computations