Getting ready for Tuesday's class

Just wanted to remind you of a few things for next class:

1. It might not have been clear in the last class, but we are using the convention that the "empty product" is defined to be 1. I.e., $\prod_{i \in \emptyset} x_i$ is taken to mean 1. In particular, the "empty parity" $\chi_\emptyset$ is the function that is 1 on every input string.

2. A trivial fact that one can sometimes forget: If $f$ is parity function itself, say $\chi_T$, then its Fourier expansion is just $\chi_T$. In other words, $\widehat{\chi_T}(S) = 1$ if $S = T$ and $= 0$ if $S \neq T$.

3. We'll use the Chernoff given on the homework, as follows: If |Pr[Test passes in case A] - Pr[Test passes in case B]| $\geq \epsilon$, then you can tell with high confidence if you're in case A or case B after $O(1/\epsilon^2)$ tests.

4. One of you will be scribing!