Testing low-degree polynomials over

Abstract. We describe an efficient randomized algorithm to test if a given binary function is a low-degree polynomial (that is, a sum of low-degree monomials). For a ���� � given integer and a ���� � given real, � the � algorithm �� � �� � ������ � queries at � points. If is a polynomial of degree at most, the algorithm always accepts, and if the value � of has to be modified on � at � least an fraction of all inputs in order to transform it to such a polynomial, then the algorithm rejects with probability ���� � at least. Our result is essentially tight: Any algorithm degree- � for testing �������� � polynomials over must perfor