Room 318

(PhD Thesis Defense) New Results in Bounds for positiveness of Polynomials

Swaroop NP

IMSc, HBNI

In this thesis we study the problem of deriving upper bounds on the positiveness of real polynomials. Such bounds have applications in algorithms for root isolation and approximation. Hence, bounds on positiveness need to efficiently computable. In the first part of the thesis, we focus on a well known bound for univariate polynomials due to Hong and a subsequent improvement over it due to Collins. Specifically, we show that unlike the Hong's bound, Collin's bound does not admit a linear time algorithm. In the multivariate
setting, we derive a bound which improves upon the best known bound due to Hong. Our improved bound is derived by generalising a well known bound for univariate real polynomials due to Lagrange. Then, we give an algorithm
to compute our improved bound and the running time of our algorithm matches the running time of the algorithm to compute Hong's bound. Our algorithm uses range trees for range querying. This motivates the question of how
efficiently can we do range querying? Specifically, we focus on the tradeoff between storage and output complexity of data structures for range querying. In the second part, we show that a lower bound on the tradeoff
between storage and output complexity due to Fredman can be strengthened. Our result implies that range trees are near optimal for range querying.