Efficiently testing sparse \(\text{GF}(2)\) polynomials

DOI10.1007/s00453-010-9426-9zbMath1225.68100MaRDI QIDQ644810

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

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

randomized algorithms; property testing; sparse polynomials; GF(2) polynomials

Mathematics Subject Classification ID

68Q32: Computational learning theory

11Y16: Number-theoretic algorithms; complexity

68W20: Randomized algorithms

Related Items

Almost optimal proper learning and testing polynomials, Almost Optimal Testers for Concise Representations.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On learning multivariate polynomials under the uniform distribution
• Testing juntas
• Learning sparse multivariate polynomials over a field with queries and counterexamples.
• Self-testing/correcting with applications to numerical problems
• Simple learning algorithms using divide and conquer
• Testing Halfspaces
• Property testing and its connection to learning and approximation
• Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• On Learning Ring-Sum-Expansions
• Approximating the Number of Zeroes of a GF[2 Polynomial]
• Simple Learning Algorithms for Decision Trees and Multivariate Polynomials
• Testing Basic Boolean Formulae
• Randomized Interpolation and Approximation of Sparse Polynomials