| Testing low-degree polynomials over GF(2) (2008) | |||||||||||||||
Abstract | |||||||||||||||
| 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 for testing degree- � polynomials over � � �� � must perform � � � � � �� � queries. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||