Refined Asymptotics for Multigraded Sums of Squares

Details Refined Asymptotics for Multigraded Sums of Squares Refined Asymptotics for Multigraded Sums of Squares

2009-01-23

arxiv.org/abs/0901.3786v3

Mathematics

Algebraic Geometry

There is an error invalidating the bounds of our main theorem. We are withdrawing this paper until we can replace it with a co

Scientific paper

To prove that a polynomial is nonnegative on R^n one can try to show that it is a sum of squares of polynomials (SOS). The latter problem is now known to be reducible to a semidefinite programming (SDP) computation much faster than classical algebraic methods, thus enabling new speed-ups in algebraic optimization. However, exactly how often nonnegative polynomials are in fact sums of squares of polynomials remains an open problem. Blekherman was recently able to show that for degree k polynomials in n variables -- with k>=4 fixed -- those that are SOS occupy a vanishingly small fraction of those that are nonnegative on R^n, as n tends to infinity. With an eye toward the case of small n, we refine Blekherman's bounds by incorporating the underlying Newton polytope, simultaneously sharpening some of his older bounds along the way. Our refined asymptotics show that certain Newton polytopes may lead to families of polynomials where efficient SDP can still be used for most inputs.

Affiliated with

Also associated with

No associations

Rating

Refined Asymptotics for Multigraded Sums of Squares 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 Refined Asymptotics for Multigraded Sums of Squares, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Refined Asymptotics for Multigraded Sums of Squares will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-454265