Title: A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation,
Abstract: In this paper, we investigate property testing whether or not a degree d
multivariate poly- nomial is a sum of squares or is far from a sum of squares.
We show that if we require that the property tester always accepts YES
instances and uses random samples, $n^{\Omega(d)}$ samples are required, which
is not much fewer than it would take to completely determine the polynomial. To
prove this lower bound, we show that with high probability, multivariate
polynomial in- terpolation matches arbitrary values on random points and the
resulting polynomial has small norm. We then consider a particular polynomial
which is non-negative yet not a sum of squares and use pseudo-expectation
values to prove it is far from being a sum of squares.