Homework #3 graded

I graded Homework #3. The mean and median were both 39/50, with a high score of 48/50.

Kudos to Runting Shi and Yi Wu for (implicitly, by giving correct answers) noticing that the weighting function in (6b) is a sum of Kravchuk polynomials, not a Kravchuk polynomials as I mistakenly wrote in the solutions.

Kudos also to Ryan Williams for improving the upper bound in problem 1 in some cases: He showed $\left(f\right)\le (2-2\alpha /(1+\alpha \left)\right)w$ when $f$ is a DNF of width $w=\alpha n$. Note that this is tight in the case $\alpha =1$, by the Parity function.

Open problem note: I'm guessing that indeed $\left(f\right)\le w$ for any width-$w$ DNF. Might be a nice thing to try to prove, although I couldn't guarantee that it isn't already known.