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 \varnothing }{x}_i$ is taken to mean 1. In particular, the "empty parity" ${\chi }_{\varnothing }$ 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}\left(S\right)=1$ if $S=T$ and $=0$ if $S\ne 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]| $\ge \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!