| The DMM bound: multivariate (aggregate) separation bounds (2009) | |||||||||||||
Abstract | |||||||||||||
| In this paper we present aggregate separation bounds for polynomials systems. We call the bounds Davenport-Mahler-Mignotte (\dmm), and we prove that in most of the cases are close to optimal. The bounds are output-sensitive in the sense that they depend on the mixed volume of the tested systems. As a consequence, we improve the gap theorem \cite{c-crmp-87} of Canny by a factor of $d^{n-1}$, where $d$ is a bound on the degree of the polynomials, and $n$ is their number. We apply our bounds on the problem of computing the eigenvalues and eigenvectors of an integer matrix, and we improve the bound of \cite{bsr-arxix-2009} on the minimum of value of a positive polynomial over the standard simplex. We also apply our bounds to find a lower bound on the number of steps that a subdivision-based algorithm for polynomial system solving should perform, we provide for the first time the complexity of Milne's algorithm in the 2D | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||