Hardness of Reconstructing Multivariate Polynomials over Finite Fields

DOI10.1137/070705258zbMath1211.68210OpenAlexW2017008844MaRDI QIDQ3068644

Parikshit Gopalan, Subhash A. 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

computational learningcoding theoryhardness of approximationlow-degree multivariate polynomialspolynomial reconstruction problem

Mathematics Subject Classification ID

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

Related Items (3)

NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem ⋮ On the hardness of learning intersections of two halfspaces ⋮ Unnamed Item

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