Hardness of Reconstructing Multivariate Polynomials over Finite Fields

DOI10.1137/070705258MaRDI QIDQ3068644zbMATH OpenOpenAlexFDO

Authors Parikshit Gopalan, Subhash Khot, Rishi Saket

Publication date 17 January 2011

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

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

zbMATH Keywords

coding theorycomputational learninghardness of approximationlow-degree multivariate polynomialspolynomial reconstruction problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational learning theory (68Q32)

Recommendations

• Factoring Multivariate Polynomials over Large Finite Fields
• Multiplicative complexity of polynomial multiplication over finite fields
• On evaluating multivariate polynomials over finite fields
• On the deterministic complexity of factoring polynomials over finite fields
• On the evaluation of multivariate polynomials over finite fields
• Factoring multivariate polynomials over finite fields
• Factorization of Multivariate Polynomials Over Finite Fields
• Polynomial multiplication over finite fields: from quadratic to straight-line complexity
• STACS 2005

Cited in

(8)

• Learning polynomials with queries: The highly noisy case
• Random Low Degree Polynomials are Hard to Approximate
• Random low-degree polynomials are hard to approximate
• NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
• Hardness results for agnostically learning low-degree polynomial threshold functions
• scientific article; zbMATH DE number 7053310 (Why is no real title available?)
• On the hardness of learning intersections of two halfspaces
• Improved hardness results for learning intersections of halfspaces

This page was built for publication: Hardness of Reconstructing Multivariate Polynomials over Finite Fields

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