The telepathic capabilities of some of you are weaker than I hoped, and so I have to better clarify some of the questions from home assignment #4.
In question 1(b), you should show that for every odd $n$, the majority function over $n$ coordinates has the highest weight on the first level out of all transitive Boolean functions on $\{-1,1\}^n$ (recall that the weight of a function $f$ on the first level is $||f^{=1}||_2^2$). You are then required to compute the limit of the weight of majority on the first level where the number of coordinates tends to infinity.
In question 3, you are required to accomplish the amazing feat of testing whether three functions are correct code-words, and in addition verifying that they satisfy an elaborate constraint, by looking at three bits total. But is this really so amazing? We know how to test that a string is a Hadamard code-word by looking at three bits, and testing whether one function equals the product of the other with a given character is really easy with even two bits queries, so we could just toss some coin and use the outcome to decide to test one of the properties that the functions need to satisfy. To pass this combination-test with very high probability, the functions must indeed satisfy (or be close to satisfying) all the required properties.
So the amazing part is actually not the fact that you can test all these things by three bit queries, it is the fact that you can do this and maintain optimal soundness (namely $\frac12+\delta$) - to get that you really have to use the same three bits to test all properties at once. By the way, the fact that $\frac12$ is the 'true' soundness barrier is not obvious here, since we are not restricting ourselves to multiplicative tests, but it is known to actually be optimal.
Question 4 deals with yet another amazing feat - testing the long-code with just two queries. And if this isn't enough, in the first part of question 5 you are asked (or at least, I meant to ask) to extend the test from question 4 to one that still uses just two bit-queries, and tests two strings for both being long-code words and for satisfying a given permutation constraint. The requirement for soundness $\delta(\epsilon)$ is a mistake - it should read $1-\epsilon-\delta(\epsilon)$, same as the expression in question 4.
In section 5(b), you need to use the test from the previous section to show a hardness of approximation result. Since I didn't yet show in class how to obtain hardness results from tests, I'll consider sections 5(a) and 5(b) as two separate questions. Moreover, you may defer submitting the answer to question 5(b) to the next exercise. However, if you choose to take a stab at it and submit it with the current exercise, you'll get a 10 point bonus if you solve the section correctly.
In question 1(b), you should show that for every odd $n$, the majority function over $n$ coordinates has the highest weight on the first level out of all transitive Boolean functions on $\{-1,1\}^n$ (recall that the weight of a function $f$ on the first level is $||f^{=1}||_2^2$). You are then required to compute the limit of the weight of majority on the first level where the number of coordinates tends to infinity.
In question 3, you are required to accomplish the amazing feat of testing whether three functions are correct code-words, and in addition verifying that they satisfy an elaborate constraint, by looking at three bits total. But is this really so amazing? We know how to test that a string is a Hadamard code-word by looking at three bits, and testing whether one function equals the product of the other with a given character is really easy with even two bits queries, so we could just toss some coin and use the outcome to decide to test one of the properties that the functions need to satisfy. To pass this combination-test with very high probability, the functions must indeed satisfy (or be close to satisfying) all the required properties.
So the amazing part is actually not the fact that you can test all these things by three bit queries, it is the fact that you can do this and maintain optimal soundness (namely $\frac12+\delta$) - to get that you really have to use the same three bits to test all properties at once. By the way, the fact that $\frac12$ is the 'true' soundness barrier is not obvious here, since we are not restricting ourselves to multiplicative tests, but it is known to actually be optimal.
Question 4 deals with yet another amazing feat - testing the long-code with just two queries. And if this isn't enough, in the first part of question 5 you are asked (or at least, I meant to ask) to extend the test from question 4 to one that still uses just two bit-queries, and tests two strings for both being long-code words and for satisfying a given permutation constraint. The requirement for soundness $\delta(\epsilon)$ is a mistake - it should read $1-\epsilon-\delta(\epsilon)$, same as the expression in question 4.
In section 5(b), you need to use the test from the previous section to show a hardness of approximation result. Since I didn't yet show in class how to obtain hardness results from tests, I'll consider sections 5(a) and 5(b) as two separate questions. Moreover, you may defer submitting the answer to question 5(b) to the next exercise. However, if you choose to take a stab at it and submit it with the current exercise, you'll get a 10 point bonus if you solve the section correctly.
No comments:
Post a Comment