Events Calendar

Speaker

Mehrdad Moharrami

Abstract

Identifying a hidden structure in a graph is a problem that occurs in many applications, including community detection, computer vision, and social networks. In this talk, we consider one such problem in which there is a bipartite graph with a hidden matching whose edge weights are lower, on average, than the weight of all the other edges in the graph. The goal is to understand the fundamental limits of when such a hidden matching can be recovered. Specifically, we show that if the average weight of the planted edge of any vertex is at least four times smaller than the average minimum weight of the other edges associated with it, then almost perfect recovery is possible. Otherwise, it is computationally infeasible. The talk is based on a paper that appeared in the Annals of Applied Probability in 2021. We will conclude the talk with other examples of learning and inference problems in graphs with societal applications.

Bio

Mehrdad Moharrami is a TRIPODS Postdoctoral Research Fellow at the University of Illinois at Urbana Champaign. He received his B.Sc. from the Sharif University of Technology, Iran, in Mathematics, as well as Electrical Engineering. He holds an M.Sc. in Electrical Engineering and an M.Sc. in Mathematics from the University of Michigan. He received his Ph.D. in Electrical Engineering in Winter 2020, for which he was awarded the Rackham Predoctoral Fellowship for an outstanding dissertation. His research interests are random graph models for economics, learning, and computation, Markov decision processes, and reinforcement learning.