Algorithms Guest Lecture with Prof Sanjeev Khanna

Mark your calendars for Algorithms Guest Lecture with Prof Sanjeev Khanna: Computing with really small space — the power of randomization! This event is for students who:

The event will begin with a brief introduction of the professor, his background, and research interests; as well as some general Q&A, time permitting.We will then move onto the guest lecture that the professor has prepared specifically for this event

In this talk we will show two simple examples that illustrate the surprising power of randomization in processing large amounts of data using very small space. Popular websites often maintain statistics about users that visit them. For instance, a website may wish to track the number of unique visitors every day. Alternately, a website may want to sample a random user active at any point during the day. Both these problems can be modeled as problems on a sequence of integers, and can be easily solved by maintaining a table of size N if the integers in the sequence are drawn from the range 1 to N. We will show that using randomization, these problems can be solved using significantly smaller space, in fact not much more than the space needed to simply write down the answer

Sanjeev Khanna is a Henry Salvatori Professor of Computer and Information Science at University of Pennsylvania. He received a Ph.D. in Computer Science from Stanford University in 1996. He joined University of Pennsylvania in 1999 after spending three years as a researcher at Bell Laboratories. Sanjeev’s primary research interests are in approximation algorithms and hardness of approximation, combinatorial optimization, and sublinear algorithms. He is an ACM Fellow, Guggenheim Fellow, and a Sloan Fellow. He is also a recipient of S. Reid Warren, Jr. and Lindback awards for distinguished teaching at University of Pennsylvania.