Efficiently Testing Sparse GF(2) Polynomials
Ilias Diakonikolas,
Homin Lee, Kevin Matulef, Rocco Servedio, Andrew Wan
35th International Colloquium on Automata, Languages and Programming (ICALP), 2008
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 epsilon-far from every
such polynomial. Our algorithm makes poly(s,1/epsilon)
black-box queries to f and runs in
time n ∙ poly(s,1/epsilon). The
only previous algorithm for this testing problem \cite{DLM+:07} used
poly(s,1/epsilon) queries, but had running time exponential in s and
super-polynomial in 1/epsilon.
Our approach significantly extends the ``testing by implicit learning'' methodology of Diakonikolas et al. \cite{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 \cite{SchapireSellie:96}. A crucial element of this work, which enables us to simulate the membership queries required by \cite{SchapireSellie:96}, is an analysis establishing new properties of how sparse GF(2) polynomials simplify under certain restrictions of ``low-influence'' sets of variables.
Conference version: [PDF]
Full version: [PDF]
Arxiv report: [arXiv]