## 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 $\mathbb{F}_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.

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment