Thursday, February 22, 2007

Learning low-degree polynomials over GF(2)

From the lecture on learning juntas, I skipped the learning-theoretic proof that when learning 2-multilinear polynomials of degree at most e, any degree-e polynomial consistent with enough data will with high probability be the truth. The very short proof, using a result from Homework 2, is here.

No comments: