Nearly sharp complexity bounds for multiprocessor algebraic computations

DOI10.1006/JCOM.1997.0436zbMATH Open0872.68053OpenAlexW1969540178MaRDI QIDQ1361876FDOQ1361876

Authors: Dima 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

Recommendations

• Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems
• scientific article; zbMATH DE number 515222
• Lower bounds for arithmetic networks. II: Sum of Betti numbers
• scientific article; zbMATH DE number 1775437

zbMATH Keywords

multiprocessor algebraic computation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• Complexity lower bounds for approximation algebraic computation trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1361876)