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 -multilinear polynomials of degree at most , any degree- polynomial consistent with enough data will with high probability be the truth. The very short proof, using a result from Homework 2, is here.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment