Efficiently testing sparse GF(2) polynomials

DOI10.1007/S00453-010-9426-9MaRDI QIDQ644810zbMATH OpenOpenAlexFDO

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

Publication date 7 November 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-010-9426-9

zbMATH Keywords

GF(2) polynomialsproperty testingrandomized algorithmssparse polynomials

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Computational learning theory (68Q32) Randomized algorithms (68W20)

Recommendations

• Efficiently Testing Sparse 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

Cites work

• Approximating the Number of Zeroes of a GF[2] Polynomial
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 5057523 (Why is no real title available?)
• scientific article; zbMATH DE number 4182832 (Why is no real title available?)
• Interpolation and Approximation of Sparse Multivariate Polynomials over GF(2)
• Learning sparse multivariate polynomials over a field with queries and counterexamples.
• On learning multivariate polynomials under the uniform distribution
• On Learning Ring-Sum-Expansions
• Property testing and its connection to learning and approximation
• Property testing. A learning theory perspective
• Randomized Interpolation and Approximation of Sparse Polynomials
• Self-testing/correcting with applications to numerical problems
• Simple Learning Algorithms for Decision Trees and Multivariate Polynomials
• Simple learning algorithms using divide and conquer
• Testing Basic Boolean Formulae
• Testing Halfspaces
• Testing juntas

Cited in

(6)

• Binomiality testing and computing sparse polynomials via witness sets
• Efficiently Testing Sparse GF(2) Polynomials
• Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Almost Optimal Testers for Concise Representations.
• Almost optimal proper learning and testing polynomials

This page was built for publication: Efficiently testing sparse \(\text{GF}(2)\) polynomials

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