Hi -- two more corrections for Homework 3. I guess this is what you get when running a course for the first time...
Question 1: Eliminate the part "and show that this is tight". In fact, I strongly believe it's not tight. For extra credit, improve on the constant factor 2.
Question 3a: This one is too hard. I thought I knew an easy way to do it, but I was mistaken. For the story on this problem, see this paper of Amano and Maruoka (but note that the theorem in their paper improving on KKL was already known).
A corrected version of the homework is on the course web page.
--------
Two small additional clarifications: In 4a, you may assume the algorithm knows $\|\hat{f}\|_1$. In 5a, as Aaron pointed out, it would probably be more sensible if I asked for you to show the estimate is within $\sqrt{\epsilon/n^d}$ rather than $\epsilon$; however, it doesn't really matter since $\epsilon$ is a parameter.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment