123 citations · 479 across the 28 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2018★ 2 cited
A theory of NP-completeness and ill-conditioning for approximate real computations
Gregorio Malajovich, Mike Shub
We develop a complexity theory for approximate real computations. We first produce a theory for exact computations but with condition numbers. The input size depends on a condition…
cs.CC2007★ 36 cited
A Numerical Algorithm for Zero Counting. I: Complexity and Accuracy
Felipe Cucker, Teresa Krick, Gregorio Malajovich +1
We describe an algorithm to count the number of distinct real zeros of a polynomial (square) system f. The algorithm performs O(n D kappa(f)) iterations where n is the number of po…
cs.CC2004★ 13 cited
Computing Multi-Homogeneous Bezout Numbers is Hard
Gregorio Malajovich, Klaus Meer
The multi-homogeneous Bezout number is a bound for the number of solutions of a system of multi-homogeneous polynomial equations, in a suitable product of projective spaces. Given…