Wednesday, January 31, 2007

Håst-Odd as a Dictatorship vs. Quasirandom test

At the end of last class I stated a proposition we'll need, which says that an $(\epsilon^2, \delta)$-quasirandom function passes the Håst-Odd${}_\delta$ test with probability at most $1/2 + \epsilon/2$.

I meant to prove it at the beginning of tomorrow's class but, surprise surprise, it looks like we'll be pressed for time even with out it. So it goes, as Vonnegut would say.

Here then, is the analysis. Really, it's pretty easy. It basically proves itself.