Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

Parikshit Gopalan Subhash Khot Rishi Saket

Published in: SIAM J. Comput. (2010)

Keyphrases

multivariate polynomials
agnostic learning
uniform distribution
noise tolerant
membership queries
pac learning
binary classification problems
target function
multi class
phase transition
learning theory
boosting algorithms
term dnf