Optimal testing of multivariate polynomials over small prime fields

DOI10.1137/120879257MaRDI QIDQ2840981zbMATH OpenOpenAlexFDO

Authors Elad Haramaty, Amir Shpilka, Madhu Sudan

Publication date 24 July 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/120879257

zbMATH Keywords

low-degree polynomialsproperty testingReed-Mullersublinear time algorithms

Mathematics Subject Classification ID

General topics in the theory of computing (68Q01) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Recommendations

• Testing low-degree polynomials over prime fields
• Deterministic irreducibility testing of polynomials over large finite fields
• Toward randomized testing of q-monomials in multivariate polynomials
• scientific article; zbMATH DE number 7758310
• Randomness efficient identity testing of multivariate polynomials
• The complexity of testing monomials in multivariate polynomials
• Testing Polynomials over General Fields
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Primality testing and Abelian varieties over finite fields

Cited in

(18)

• Testing low-degree polynomials over prime fields
• A new upper bound on the query complexity of testing generalized Reed-Muller codes
• Testing Polynomials over General Fields
• scientific article; zbMATH DE number 1003235 (Why is no real title available?)
• On higher-order Fourier analysis over non-prime fields
• Robust multiplication-based tests for Reed-Muller codes
• Optimal testing of Reed-Muller codes
• Local decoding and testing of polynomials over grids
• Local decoding and testing of polynomials over grids
• Reed-Muller Codes
• Hard functions for low-degree polynomials over prime fields
• Hard functions for low-degree polynomials over prime fields
• Hypercontractivity for global functions and sharp thresholds
• One-sided error testing of monomials and affine subspaces
• Property testing with online adversaries
• Improved optimal testing results from global hypercontractivity
• Property testing with online adversaries
• Structural testing with homomorphic encryption

This page was built for publication: Optimal testing of multivariate polynomials over small prime fields

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