| Polynomials of Bounded Tree-Width (Extended Abstract) (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. We introduce a new sparsity conditions on multivariate polynomials in n variables (over some ring R) and show that under this condition many otherwise intractable computational problems involving these polynomials become solvable in polynomial (even linear) time in n (in the BSS-model over R). To define our sparsity condition we associate with these polynomials a hypergraph and study classes of polynomials where this hypergraph has tree width at most k for some fixed k 2 N. We are interested in three cases: (1) The evaluation of multivariate polynomials where the number of monomials is O(2 n (2) The question whether a system of n polynomials p i (x) 2 R[x] of fixed degree d in n variables has a root in R n (3) For infinite ordered rings Rord, a polynomial of fixed degree d in n variables p(x) 2 Rord [x] and a finite subset A ae Rord we want to know whether p(a) ? 0 for all a 2 R n ord. Our method uses graph theoretic and model theoretic tools developed in the last 15 years and applies them to the algebraic setting. This work is an | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||