Title: Error-correcting codes as pseudorandom generators

Speaker: Michael Crouch, UMass Amherst

Abstract: 

Randomized algorithms often do not need completely independent random numbers; they may require a long string of random numbers which satisfy certain limited independence properties.  Pseudorandom generators allow us to efficiently reconstruct a long "random-looking" string from a small random seed.  They see particular use in streaming algorithms, where we do not have enough memory space to store all of the random decisions the algorithm needs to make, and must calculate them as-needed from the small seed.

In this talk I will review several error-correcting codes which are used as pseudorandom generators.  I will describe the limited-independence properties which allow these codes to be used in streaming algorithms.  I will then present recent results by Tirthapura and Woodruff which show how the recursive structures of these codes can be exploited to decrease per-element processing times in existing streaming algorithms.  Attendees are encouraged to bring lunch.