Joint Theory Seminar / Computer Science Speaking Skills Talk
— 1:00pm
Location:
In Person and Virtual - ET
-
Gates Hillman 8102 and Zoom
Speaker:
PRANEETH KACHAM
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.praneethkacham.com/
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.
Event Website:
https://www.cs.cmu.edu/~theorylunch/