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

property testinglow-degree polynomialssublinear time algorithmsReed-Muller

Mathematics Subject Classification ID

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

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

(12)

• On higher-order Fourier analysis over non-prime fields
• Local decoding and testing of polynomials over grids
• Local decoding and testing of polynomials over grids
• Hypercontractivity for global functions and sharp thresholds
• A new upper bound on the query complexity of testing generalized Reed-Muller codes
• Hard functions for low-degree polynomials over prime fields
• Reed-Muller Codes
• Hard functions for low-degree polynomials over prime fields
• Robust multiplication-based tests for Reed-Muller codes
• Testing low-degree polynomials over prime fields
• Testing Polynomials over General Fields
• Optimal testing of Reed-Muller codes

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)