- Start Date:
July 12, 2016
- Event Start Time:
10:00 AM
- Event End Time:
11:00 AM
- Organizers:
Lazaros Gallos
- Seminar Series:
REU Seminar
- Presenter(s):
Periklis Papakonstantinou - Rutgers University
- Event Location:
DIMACS Seminar room
- Abstract:
Imagine that you are using a computational device -- e.g. your laptop or even a server -- that is much weaker than a huge stream of data -- e.g. scan through the data stored in one of google's data centers -- you are asked to process. The whole point is that (i) the "local memory" of your device is much smaller than the amount of data you are processing and (ii) the device is restricted to access these data as stream presented in a bit-by-bit fashion (and at a high rate).
Here a "device" is an abstraction. It can be either some specialized hardware, or "device" is a Python program running in your laptop, or a steam-powered Turing Machine that reads its input tape from left-to-right.
I shall discuss in detail two of my favorite results in single-stream algorithms: distinct-elements-counting and frequency-moment-estimation. This development is based on families of universal hash functions -- an extremely useful object in various ways. Then, I shall go on and introduce you to the recently introduced, wonderful world of multi-stream algorithms.
No prior knowledge in streaming or pseudo-randomness is required.
