Timeline for Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 8, 2012 at 17:48 | comment | added | Suvrit | Sorry, somehow in my excitement, I suppressed $i$ and $k$ being free parameters (I just read them as summation indices); maybe you might want to call them $m$ and $n$ to ameliorate dumb oversights like mine! | |
| Aug 8, 2012 at 17:37 | comment | added | Ryan O'Donnell | Hi Suvrit, thanks for the comments. I mean specifically for the family of polynomials (parameterized by i and k) in the question. I thought perhaps that if one could give a recurrence relation for the polynomials, it might become clear that they are nonnegative... | |
| Aug 8, 2012 at 17:32 | history | edited | Suvrit | CC BY-SA 3.0 |
clarified the contents of the stuff that I wrote.
|
| Aug 8, 2012 at 17:16 | comment | added | Suvrit | Indeed, each specific case is "routine", though it is worth noting here that if the degree of the polynomial gets high enough, then you'll probably have to give up maple, and use an SDP solver. When you say certifying for families, do you have a parameterized class in mind; in that case, one could see if the resulting parametric SDP can be solved in polynomial time, though I am not that too certain about that. | |
| Aug 8, 2012 at 16:50 | comment | added | Ryan O'Donnell | Right, that's really what I meant about each specific case being 'routine'; you can certify that a given matrix with rational entries is PSD in polynomial time. The question is about doing it for families of polynomials. | |
| Aug 8, 2012 at 16:41 | history | answered | Suvrit | CC BY-SA 3.0 |