I have a multivariate polynomial $p(x_1,\ldots,x_n)$ and I wish to check if it is positive semidefinite over $R^n$. I can always choose any direction $\vec{v}$ and check that the univariate polynomial $q(x) = p( x\vec{v})$ is positive semidefinite. Imagine sampling $\vec{v}$ and testing. Univariate polynomials are easy to test for p.s.d. If I get lucky and a direction fails the univariate test, I can conclude that $p$ is not positive semidefinite.
Question is whether there is any known result in this space that will allow me to conclude that the polynomial is positive semidefinite after testing finitely many directions?
My motivation: I am looking for a randomized algorithm for positive semidefiniteness testing much like the identity testing algorithm that is based on Schwarz Zippel Lemma.
thanks, Sriram
