Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond

Details Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond

2011-01-13

arxiv.org/abs/1101.2642v1

Mathematics

Algebraic Geometry

20 pages, 5 figures, submitted to a refereed conference proceedings

Scientific paper

Suppose f is a real univariate polynomial of degree D with exactly 4 monomial terms. We present an algorithm, with complexity polynomial in log D on average (relative to the stable log-uniform measure), for counting the number of real roots of f. The best previous algorithms had complexity super-linear in D. We also discuss connections to sums of squares and A-discriminants, including explicit obstructions to expressing positive definite sparse polynomials as sums of squares of few sparse polynomials. Our key tool is the introduction of efficiently computable chamber cones, bounding regions in coefficient space where the number of real roots of f can be computed easily. Much of our theory extends to n-variate (n+3)-nomials.

Affiliated with

Also associated with

No associations

Rating

Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67185