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.

## Wednesday, January 31, 2007

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment