Joint Theory Seminar / Computer Science Speaking Skills Talk
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.