Jose writes: "if you have a polynomial that is positive semidefinite, more likely than not it is a sum of squares"

This sort of statement is very sensitive to what probability distribution you use on the space of all polynomials. I am sure there are formulations in which it is true; here is one in which it is false.

Fix d greater than 1. Let Poly(2d,n) be the vector space of homogenous*, degree 2d polynomials in n variables. Let's choose polynomials uniformly at random from unit sphere in this space. Blekherman has computed that the probability that a polynomial is positive is ~ n^{-1/2}, while the probability that it is a sum of squares is ~ n^{-d/2}. So, for n large, almost all positive polynomials are not sums of squares.

Blekherman also has a recent preprint showing that, in the same sense, almost all positive convex polynomials are not sums of squares.

* If you don't like working with homogenous polynomials, notice that Poly(2d,n) is also the vector space of inhomogenous polynomials in n-1 variables with degree at most d. Just plug in 1 for the last variable. Under this correspondence, a polynomial is nonnegative on R^n if and only if it is nonnegative on R^{n-1} x {1}. The property of being strictly positive is not preserved by this transformation, but the polynomials which are nonnegative and not strictly positive form a set of measure 0.

Jose writes: "if you have a polynomial that is positive semidefinite, more likely than not it is a sum of squares"

This sort of statement is very sensitive to what probability distribution you use on the space of all polynomials. I am sure there are formulations in which it is true; here is one in which it is false.

Fix d greater than 1. Let Poly(2d,n) be the vector space of homogenous*, degree 2d polynomials in n variables. Let's choose polynomials uniformly at random from unit sphere in this space. Blekherman has computed that the probability that a polynomial is positive is ~ n^{-1/2}, while the probability that it is a sum of squares is ~ n^{-d/2}. So, for n large, almost all positive polynomials are not sums of squares.

Blekherman also has a recent preprint showing that, in the same sense, almost all positive convex polynomials are not sums of squares.

* If you don't like working with homogenous polynomials, notice that Poly(2d,n) is also the vector space of inhomogenous polynomials in n-1 variables with degree at most d. Just plug in 1 for the last variable. Under this correspondence, a polynomial is nonnegative on R^n if and only if it is nonnegative on R^{n-1} x {1}. The property of being strictly positive is not preserved by this transformation, but the polynomials which are nonnegative and not strictly positive form a set of measure 0.

Jose writes: "if you have a polynomial that is positive semidefinite, more likely than not it is a sum of squares"

This sort of statement is very sensitive to what probability distribution you use on the space of all polynomials. I am sure there are formulations in which it is true; here is one in which it is false.

Fix d greater than 1. Let Poly(2d,n) be the vector space of homogenous, degree 2d polynomials in n variables. Let's choose polynomials uniformly at random from unit sphere in this space. Blekherman has computed that the probability that a polynomial is positive is ~ n^{-1/2}, while the probability that it is a sum of squares is ~ n^{-d/2}. So, for n large, almost all positive polynomials are not sums of squares.

Blekherman also has a recent preprint showing that, in the same sense, almost all positive convex polynomials are not sums of squares.

Jose writes: "if you have a polynomial that is positive semidefinite, more likely than not it is a sum of squares"

This sort of statement is very sensitive to what probability distribution you use on the space of all polynomials. I am sure there are formulations in which it is true; here is one in which it is false.

Fix d greater than 1. Let Poly(2d,n) be the vector space of homogenous*, degree 2d polynomials in n variables. Let's choose polynomials uniformly at random from unit sphere in this space. Blekherman has computed that the probability that a polynomial is positive is ~ n^{-1/2}, while the probability that it is a sum of squares is ~ n^{-d/2}. So, for n large, almost all positive polynomials are not sums of squares.

Blekherman also has a recent preprint showing that, in the same sense, almost all positive convex polynomials are not sums of squares.

* If you don't like working with homogenous polynomials, notice that Poly(2d,n) is also the vector space of inhomogenous polynomials in n-1 variables with degree at most d. Just plug in 1 for the last variable. Under this correspondence, a polynomial is nonnegative on R^n if and only if it is nonnegative on R^{n-1} x {1}. The property of being strictly positive is not preserved by this transformation, but the polynomials which are nonnegative and not strictly positive form a set of measure 0.