Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

Parikshit Gopalan Subhash Khot Rishi Saket

Published in: Electron. Colloquium Comput. Complex. (2007)

Keyphrases

multivariate polynomials
agnostic learning
uniform distribution
pac learning
computational complexity
target function
noise tolerant
np hard
information theoretic
decision lists