Computer Science Speaking Skills Talk
— 3:00pm
Location:
In Person
-
Gates Hillman 7501
Speaker:
PRANEETH KACHAM
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.praneethkacham.com/
Fast streaming algorithms via a new Pseudorandom Generator
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.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.