### Abstract

We describe an efficient randomized algorithm to test if a given binary function f : {0, 1}^{n} → {0, 1} is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k ≥ 1 and a given real ε > 0, the algorithm queries f at O(1/ε + k4^{k}) points. If f is a polynomial of degree at most k, the algorithm always accepts, and if the value of f 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 2/3. Our result is essentially tight: Any algorithm for testing degree-k polynomials over GF(2) must perform Ω(1/e + 2^{k}) queries.

Original language | English (US) |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Editors | Sanjeev Asora, Amit Sahai, Klaus Jansen, Jose D.P. Rolim |

Publisher | Springer Verlag |

Pages | 188-199 |

Number of pages | 12 |

ISBN (Print) | 3540407707, 9783540407706 |

DOIs | |

State | Published - 2003 |

Externally published | Yes |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2764 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Testing low-degree polynomials over GF(2)'. Together they form a unique fingerprint.

## Cite this

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*(pp. 188-199). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2764). Springer Verlag. https://doi.org/10.1007/978-3-540-45198-3_17