Polynomials that are sums of squares Is any algorithm known for determining whether or not a multivariate polynomial with integer coefficients can be written as a sum of squares of such polynomials? 
By way of background, if we one replaces "polynomial" by "rational function" then there is such an algorithm, because a rational function is a sum of squares iff it is positive definite. But this equivalence fails for polynomials.
 A: Yes, the group of Parillo developed an algorithm and a matlab toolbox they called SOSTOOLS
There is a degree of complexity though, I am not an expert in their algorithm so I don't know how efficient their algorithm is. I remember reading that the sum of  squares polynomials are dense in the space of positive semidefinite polynomials by some norm.. I think it was L1 norm. And if you know that your polynomial is positive and convex, then its "more likely" that its a sum of squares (as far as I know, no one has yet shown that there are convex (multivariate) polynomials that are positive but not sum of squares).
A: Determining whether or not a polynomial is a sum of squares can be done in polynomial time; the problem is equivalent to semidefinite programming.  As Jose Capco mentioned above, Pablo Parrilo is an authority on this subject, and has written a number of papers explaining the relationship.
Parrilo has a particularly short, simple, and self-contained exposition of this relationship in Parrilo, Pablo A. "Sum of squares programs and polynomial inequalities." SIAG/OPT Views-and-News: A Forum for the SIAM Activity Group on Optimization. Vol. 15. No. 2. 2004.
A: 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.
