In the first part of the class, we have stated without proof that (AND,OR,NOT)-circuits of size s and depth d have "low" Fourier degree, from which it follows that they can be learned in time n^((log s)^d); this is due to Linial-Mansour-Nisan. We have then shown how to use the low-degree algorithm to learn decision lists and decision trees, and mentioned the Kushilevitz-Mansour algorithm that uses Membership Queries and can learn decision trees in polynomial time.
In the second part of the class we saw two variations on the PAC learning definition, one that fixes the confidence parameter $\delta = 1/2$, and one that fixes the accuracy parameter $\epsilon = 1/2$. We showed that the first variation is equivalent to the original one.
Exercise 24: Give depth-d circuits of size about 2^{n^{O(1/d)}} for parity of n variables. Hint: use divide-and-conquer.
Exercise 25: Use the [LMN] result on the Fourier degree of AC^0 to show that
depth-d circuits for parity of n variables must have size about 2^{n^\Omega(1/(d-1))}.
Of course, the more precise you can be in your bounds, the better solution.
No comments:
Post a Comment