A small correction for the first question in assignment #4: in section (b) you are required to show that Majority has the highest first level weight out of all *transitive* Boolean functions. Also, although I forgot to mention this in the exercise, you should also compute that weight.
Thursday, May 8, 2008
Subscribe to:
Post Comments (Atom)
2 comments:
There are a few things in question 5a that are unclear to me.
1. "Extend the test" means that it should remain a 2-query test (hinted by section 5b)? We saw a perfectly good 3-query test in class.
2. You require soundness \delta(\epsilon), which usually symbolizes a small number. Is it okay if the test has soundness 1-\delta (for small \delta)?
3. Is it okay if soundness only holds for all small enough \epsilon?
Thanks.
Hi Zvika,
I answered you questions in the new post. The answer for your third question is yes.
Best,
g
Post a Comment