Efficiently Testing Sparse GF(2) Polynomials

DOI10.1007/978-3-540-70575-8_41MaRDI QIDQ3521943zbMATH OpenOpenAlexFDO

Authors Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Andrew Wan, Rocco A. Servedio

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.1765

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Computational learning theory (68Q32) Symbolic computation and algebraic computation (68W30)

Abstract: We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function $f:{0,1}^{n}o0,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 $ncdotpoly(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.

Recommendations

• Efficiently testing sparse \(\text{GF}(2)\) polynomials
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• A local decision test for sparse polynomials
• Interpolation and Approximation of Sparse Multivariate Polynomials over GF(2)
• Testing Fourier Dimensionality and Sparsity

Cited in

(10)

• Binomiality testing and computing sparse polynomials via witness sets
• Efficient sample extractors for juntas with applications
• A local decision test for sparse polynomials
• Testing submodularity and other properties of valuation functions
• Testing by implicit learning: a brief survey
• Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
• Testing Fourier dimensionality and sparsity
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Testing Fourier Dimensionality and Sparsity
• Efficiently testing sparse \(\text{GF}(2)\) polynomials

This page was built for publication: Efficiently Testing Sparse GF(2) Polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3521943)