Room 327

New Results in Bounds for Positiveness of Polynomials

NP Swaroop

IMSc, HBNI

Proving efficient upper bounds on the positiveness of polynomials is an important question in computer algebra. Upper bound on positiveness is required for algorithms for root isolation and root approximation. In the first part of the thesis, we begin by showing that a known bound for univariate polynomials (Hong, 1998) achieves the best tradeoff between quality and computational complexity. In the multivariate setting, we give a new bound which improves upon the best known bound in the literature (Hong, 1998). We also give an algorithm for computing this improved bound and the running time of our algorithm matches the running time of the best known algorithm by Mehlhorn-Ray for computing Hong's bound.
Motivated from a question from the first part, in the second part of the thesis, we focus on strengthening a certain lower bound (Fredman, 1981) on orthogonal range querying.