Abstract
Testing properties in various models is an emerging research area. In this talk, we will focus on testing over an infinite domain, in particular, the fundamental problem of testing for a function f:R^n->R is a low total degree polynomial. This problem is trivial for univariate functions and becomes dramatically different when the domain is R^n for n being asymptomatically large. We will show a local tester for low-degree polynomials. To see that the tester is sound we will prove a "local-to-global" lemma for the property of being a polynomial of low-degree. Then, proving a stability version of this local-to-global lemma, we can build an approximate tester when only finite bits precision is available.
We will discuss some open questions and other directions for a theory of property testing over the reals.