Homework 3 Corrections

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 $\parallel \hat{f}{\parallel }_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.