Just back from EPIT 2012 where I gave four lectures on data streams and a bit of communication complexity. Other lecturers discussed semi-definite programming, inapproximability, and quantum computing. Thanks to Iordanis Kerenidis, Claire Mathieu, and Frédéric Magniez for a great week.

Anyhow, I wanted to post my slides along with some editorial comments that may or may not be of interest. Here’s the first lecture:

The goal was to cover some of the basic algorithmic techniques such as different forms of sampling and random linear projections. The basic narrative was:

*Sampling:* Sure, you can uniformly sample from the stream and try to make some inferences from the sample. But there are better ways to use your limited memory.
*Sketching:* You can compute random linear projections of the data. Hash-based sketches like Count-Min and Count-Sketch are versatile and solve many problems including quantile estimation, range queries, and heavy hitters.
*Sampling Again:* A useful primitives enabled by sketching, is non-uniform sampling such as sampling where the probability of returning a stream element of type is proportional to the -th power of the frequency of .

I bookended the lecture with algorithms for frequency moments, first a suboptimal result via AMS sampling (from Alon et al. STOC 1996) and then a near-optimal result via sampling (from Andoni et al. FOCS 2011 and Jowhari et al. PODS 2011). I was tempted to use another example but that seemed churlish given the importance of frequency moments in the development of data streams theory. To keep things simple I assumed algorithms had an unlimited source of random bits. Other than that I was quite happy that I managed to present most of the details without drowning in a sea of definitions and notation.

### Like this:

Like Loading...

*Related*

## 4 comments

Comments feed for this article

April 2, 2012 at 8:46 am

AndrewClaire has posted a more poetic take on the week here:

http://teachingintrotocs.blogspot.com/2012/04/spring-school-heaven.html

April 3, 2012 at 10:32 am

Aravind SrinivasanVery nice Andrew. These slides will help me (and am sure many others) in our teaching as well.

April 8, 2012 at 11:31 pm

AndrewThanks Aravind. If it would be helpful to have the latex source, let me know.

April 13, 2012 at 9:10 am

EPIT Lectures: Lower Bounds «[…] up in the mini-course on data streams (first two lectures here and here) were lower bounds and communication complexity. The slides are […]