Homework 5 graded

Homework 5 is graded and will be handed back tomorrow. The average was 79%.

A few comments:

1. Most people got this right (one way or another).

2. For part b), the two equally simplest counterexamples are {$x_1$, $x_1$, $1$}, or {$x_1$, $x_1$, $x_1$}. Aaron, Kanat, and Mike all gave the same, far-from-simplest counterexample. What a coincidence...

3. Many people failed to prove a characterization (if and only if statement) in c), and just gave an implication. Many people also had complicated solutions for the support-3 problem. Ali and Amitabh gave roughly the same solution, which is probably the slickest. Suppose f = a ${\chi }_S$ + $b{\chi }_T$ + $c{\chi }_U$, where the coefficients $a,b,c$ are nonzero and $S$, $T$, $U$ are distinct. By Parseval,

$a^2+b^2+c^2=1$ (*).

Substituting in $(1,...,1)$, we get $a+b+c\in -1,1$. Squaring this and subtracting (*) yields

$ab+bc+ac=0$ (**).

Since $S$, $T$, $U$ are distinct, there must be an index $i$ which is in exactly 1 or 2 of them. Substituting in the string which is 1 everywhere except that it's $-1$ on the $i$th coordinate, we conclude ${\sigma }_{1}a+{\sigma }_{2}b+{\sigma }_{3}c\in -1,1$, where exactly 1 or 2 of the signs ${\sigma }_i$ are $-1$. Squaring this and subtracting (*) yields

${\tau }_{1}ab+{\tau }_{2}bc+{\tau }_{3}ac=0$ (***),

where exactly two of the signs ${\tau }_i$ are $-1$. Now add (**) and (***) and conclude that one of $ab$, $bc$, or $ac$ must equal 0, a contradiction.

4. Most people got (a) and (b). For (c), several people estimated the degree-1 Fourier coefficients of Majority and concluded that it's, say, $(1/n,1/2)$-quasirandom. Only Eric truly ventured to high degree, pointing out that $In{f}_i\left(Maj\right)$ can be seen to be $\Theta (1/\sqrt{n})$, and therefore by 5a, Maj is $(\Theta (1/\sqrt{n}),0)$-quasirandom. In fact, one can show that the largest Fourier coefficients for Maj are the ones at level $1$, and hence Maj is $(1/n,0)$-quasirandom.

5. Most people more or less got this.

6. Most people mostly got this; the key in b) is picking the right diameter.

7. Most people got this too, although many failed to do both parts of f).