Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

Parikshit Gopalan Subhash Khot Rishi Saket

Published in: FOCS (2007)

Keyphrases

multivariate polynomials
agnostic learning
uniform distribution
pac learning
learning theory
phase transition
noise tolerant
np hard
information theoretic
machine learning
special case
target function