## Abstract

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function f: {0,1} n →{0,1} is an s-sparse GF(2) polynomial versus ε-far from every such polynomial. Our algorithm makes poly(s,1/ε) black-box queries to f and runs in time n ·poly(s,1/ε). The only previous algorithm for this testing problem [DLM + 07] used poly(s,1/ε) queries, but had running time exponential in s and super-polynomial in 1/ε.

Our approach significantly extends the “testing by implicit learning” methodology of [DLM + 07]. The learning component of that earlier work was a brute-force exhaustive search over a concept class to find a hypothesis consistent with a sample of random examples. In this work, the learning component is a sophisticated exact learning algorithm for sparse GF(2) polynomials due to Schapire and Sellie [SS96]. A crucial element of this work, which enables us to simulate the membership queries required by [SS96], is an analysis establishing new properties of how sparse GF(2) polynomials simplify under certain restrictions of “low-influence” sets of variables.

Our approach significantly extends the “testing by implicit learning” methodology of [DLM + 07]. The learning component of that earlier work was a brute-force exhaustive search over a concept class to find a hypothesis consistent with a sample of random examples. In this work, the learning component is a sophisticated exact learning algorithm for sparse GF(2) polynomials due to Schapire and Sellie [SS96]. A crucial element of this work, which enables us to simulate the membership queries required by [SS96], is an analysis establishing new properties of how sparse GF(2) polynomials simplify under certain restrictions of “low-influence” sets of variables.

Original language | English |
---|---|

Title of host publication | Automata, Languages and Programming |

Editors | Luca Aceto, Ivan Damgård, LeslieAnn Goldberg, MagnúsM. Halldórsson, Anna Ingólfsdóttir, Igor Walukiewicz |

Publisher | Springer Berlin Heidelberg |

Pages | 502-514 |

Number of pages | 13 |

Volume | 5125 |

ISBN (Electronic) | 978-3-540-70575-8 |

ISBN (Print) | 978-3-540-70574-1 |

DOIs | |

Publication status | Published - 2008 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Berlin Heidelberg |

Volume | 5125 |