Algorithms on Evolving Data
Halls department, Hall 3
Thursday, 28 December 2017
09:00 - 10:00
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.
Mohammad Mahdian is a research scientist at the Google Research lab in New York, specializing in market algorithms. He has a Ph.D. from MIT, an M.Sc. from University of Toronto, and a B.Sc. from Sharif University of Technology. Prior to Google, he has worked at Yahoo! Research and Microsoft Research