Mathematics – Algebraic Geometry
Scientific paper
2009-04-26
The final version was published in the proceedings of SNC 2009(August 3--5, 2009, Kyoto, Japan), pp. 133-142, ACM Press, 2010
Mathematics
Algebraic Geometry
9 pages, 7 figures (3 of them tiny). This is close to the final conference proceedings version
Scientific paper
We give a high precision polynomial-time approximation scheme for the supremum of any honest n-variate (n+2)-nomial with a constant term, allowing real exponents as well as real coefficients. Our complexity bounds count field operations and inequality checks, and are polynomial in n and the logarithm of a certain condition number. For the special case of polynomials (i.e., integer exponents), the log of our condition number is quadratic in the sparse encoding. The best previous complexity bounds were exponential in the sparse encoding, even for n fixed. Along the way, we extend the theory of A-discriminants to real exponents and certain exponential sums, and find new and natural NP_R-complete problems.
Pebay Philippe
Rojas Maurice J.
Thompson David C.
No associations
LandOfFree
Optimization and NP_R-Completeness of Certain Fewnomials 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 Optimization and NP_R-Completeness of Certain Fewnomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization and NP_R-Completeness of Certain Fewnomials will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-322023