Efficiently Testing Sparse GF(2) Polynomials

Details Efficiently Testing Sparse GF(2) Polynomials Efficiently Testing Sparse GF(2) Polynomials

2008-05-13

arxiv.org/abs/0805.1765v1

Computer Science

Computational Complexity

Full version of ICALP 2008 paper

Scientific paper

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function $f: \{0,1\}^n \to \{0,1\}$ is an $s$-sparse GF(2) polynomial versus $\eps$-far from every such polynomial. Our algorithm makes $\poly(s,1/\eps)$ black-box queries to $f$ and runs in time $n \cdot \poly(s,1/\eps)$. The only previous algorithm for this testing problem \cite{DLM+:07} used poly$(s,1/\eps)$ queries, but had running time exponential in $s$ and super-polynomial in $1/\eps$. Our approach significantly extends the ``testing by implicit learning'' methodology of \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.

Affiliated with

Also associated with

No associations

Rating

Efficiently Testing Sparse GF(2) Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficiently Testing Sparse GF(2) Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficiently Testing Sparse GF(2) Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-471861