Title: Communications and Data-Dependent Decision-Making: Synergies and Constraints
Date : Nov 24, 2023
Time : 4:30 PM to 5:30 PM
Venue: A-007, R & D Block, IIIT-Delhi
Abstract:
In my talk I will discuss techniques that allow for efficiently generating many independent random walks from starting from all nodes in a graph. This computational routine is often used for computing the PageRank vector which is a fundamental data science notion. I introduce how to implement such random walk generation in the context of the Massive Parallel Computation (MPC) model as well as dynamic computations. More specifically, I will discuss:
- how to maintain such a set of random walks in undirected graphs in polylogarithimic update time,
- how to compute such a set of random walks in MPC model in polyloglog time.
These results immediately lead to efficient approximation algorithms for the PageRank problem in respective scenarios.
On the negative side we provide an Ω(n^{1−δ}) lower bound for the amortized update time of any algorithm that explicitly maintains a constant multiplicative approximation of PageRank in the insertion- or deletion-only model in directed graphs, what resolves a 13-year old open question of Bahmani et al. (VLDB 2010). In order to obtain efficient algorithms, we look beyond the relative error goal, and demonstrate that a simple batch recomputation algorithm can maintain good approximations to PageRank under L_1 error. We evaluate this similar algorithm empirically and demonstrate that it delivers similar preformacje while being much simpler .
Based on joint work with Rajesh Jayaram, Kuba Łącki, Slobodan Mitrović, Krzysztof Onak.
Brief Bio: Piotr Sankowski, Polish computer scientist, habilitated doctor of mathematical sciences. Associate professor at the Institute of Computer Science, Faculty of Mathematics, Informatics and Mechanics, University of Warsaw and CEO of IDEAS NCBR, Warsaw-based research and development center operating in the field of artificial intelligence.
His research interest focuses on practical application of algorithms, ranging from economic applications, through learning data structures, to parallel algorithms for data science. In 2005, he received a doctorate in computer science, and in 2009 habilitation and doctorate in physics in the field of solid state theory at the Polish Academy of Sciences. He completed post-doctoral internships at ETH Zurich Institute of Science and Sapienza University of Rome.