Posted by: atri | April 23, 2010

## Lecture 40: Hot Items Problem

In Wednesday’s lecture, we saw a data stream algorithm for the “hot items” problem based on group testing due to Cormode and Muthukrishnan. We saw that the existing strongly explicit construction of $d$-disjunct matrix based on Reed-Solomon codes (see lecture 29) was enough to give three out of the four things we wanted in our algorithm:

• One pass
• Poly-log space
• Poly-log update time.

The only missing part was poly-log reporting time, which we tackled in Friday’s lecture.