Efficiently Testing Sparse GF(2) Polynomials

Ilias Diakonikolas, HominK. Lee, Kevin Matulef, RoccoA. Servedio, Andrew Wan

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function f:{0,1}n →{−1,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 (Diakonikolas et al. in Proceedings of the 48th Annual Symposium on Foundations of Computer Science, FOCS, pp. 549–558, 2007) 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 Diakonikolas et al. (Proceedings of the 48th Annual Symposium on Foundations of Computer Science, FOCS, pp. 549–558, 2007). 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 (J. Comput. Syst. Sci. 52(2):201–213, 1996). A crucial element of this work, which enables us to simulate the membership queries required by Schapire and Sellie (J. Comput. Syst. Sci. 52(2):201–213, 1996), is an analysis establishing new properties of how sparse GF(2) polynomials simplify under certain restrictions of “low-influence” sets of variables.
Original languageEnglish
Pages (from-to)580-605
Number of pages26
JournalAlgorithmica
Volume61
Issue number3
DOIs
Publication statusPublished - 2011

Keywords / Materials (for Non-textual outputs)

  • Property testing
  • GF(2) polynomials
  • Sparse polynomials
  • Randomized algorithms

Fingerprint

Dive into the research topics of 'Efficiently Testing Sparse GF(2) Polynomials'. Together they form a unique fingerprint.

Cite this