BARC talk by Hanzhi Wang

Tuesday, December 17, 2024, Hanzhi Wang, our new Postdoc at BARC, will give a talk on "Local Algorithms for Random-Walk Probability Estimation on Large Graphs".

Abstract:
With the advent of web and social networks, real-world scenarios often involve massive graphs with millions or even billions of nodes and edges. In such massive graphs, traditional approaches, whose time complexity can increase linearly or super-linearly with the size of the graph, become impractical. Local graph algorithms, which complete graph analysis tasks by exploring only a small fraction of the graph, are of particular interest in both theoretical studies and practical applications.

In this talk, Hanzhi will introduce her research efforts aimed at designing provable-good local algorithms for computing random-walk probabilities on large graphs, a cornerstone problem and a critical algorithmic component in graph analysis. She will begin by providing an overview of local graph algorithms and random-walk probability computations. Then, she will illustrate four different types of random-walk probability queries and summarize my contributions in achieving better complexity bounds for these query problems. Next, HanzhiI will describe several critical algorithmic techniques and demonstrate how to utilize these techniques to achieve my complexity results. Finally, she will discuss some interesting open problems in this area.

Bio:
Hanzhi Wang joined BARC on November 1, 2024, as a PostDoc, working with Professor Mikkel Thorup. Her research interests focus on graph algorithms, particularly on developing sublinear-time algorithms for large-scale graphs. Previously, she devoted her efforts to designing local algorithms for random-walk probability estimation on large graphs.
Before joining BARC, Hanzhi obtained her Ph.D. in Computer Science from Renmin University of China in May 2024, under the supervision of Professor Zhewei Wei. Prior to that, she received her B.E. degree from the same institution in 2019.