Joint Theory Seminar / Computer Science Speaking Skills Talk

— 1:00pm

In Person and Virtual - ET - Gates Hillman 8102 and Zoom

Ph.D. Student, Computer Science Department, Carnegie Mellon University

How to make streaming algorithms fast?

In this talk, I'll present our work on a new pseudorandom generator (PRG) which can be considered a generalization of Nisan's PRG. We show that the space-vs-time tradeoff presented by our Pseudorandom generator can be used to obtain streaming algorithms that are optimal in space while having a very small update time i.e., the time required for the streaming algorithm to process an update is very small. 

This talk is being presented as a part of the Theory Lunch Seminar series.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

CMU Theory Youtube channel

Event Website:

Add event to Google
Add event to iCal