Mohammad Mahdian

Staff Research Scientist, Google Research

Algorithms on Evolving Data

Location

Halls department, Hall 3

Date and Time

Thursday, 28 December 2017
09:00 - 10:00

Abstract

In many real-world applications, an algorithmic problems need to be solved on  input data sets that are constantly changing. For example, search engines need to find a ranking of web-pages based on a changing web-graph. We formulate and study a new stochastic model for computation on evolving data sets. In this framework the input data changes gradually over time and the algorithm can only track these changes by probing the data set. The goal is to maintain an output that is close to the correct output with a limit on the number of probes. We apply this framework to the problems of sorting and selection as well as the problem of community detection in networks, and obtain close-to-optimal algorithms in each case.

Bio

Mohammad Mahdian has a B.Sc. degree in computer engineering from the Sharif University of Technology, an M.Sc. from University of Toronto, and a Ph.D. from MIT. He is currently a research scientist at Google Research in New York. Prior to Google, he has worked at Yahoo! Research and Microsoft Research.