Posted by: atri | March 24, 2010

Hint on hint for HW3

After Devanshu asked a question on the hint for Q 3(a), I realized that it could be somewhat mis-leading. The hint was there to build your intuition about the problem– not directly give you the proof. An easy way to prove 3(a) would be to try to prove it by induction on the number of rows.

Please use the comments section if you have any further question. I hope the fact that I do not have official office hours did not discourage you from asking questions.

Responses

1. For the Problem1(b), is it the evaluation of the multivariate polynomial over the points in {0,1}r? Or {0,1}2^r? In the first case, the evaluation should be of dimension r, but the code word is of dimension 2^r.

• It is over $\{0,1\}^r$. Note that there are $2^r$ vectors in $\{0,1\}^r$.