Keynote Speaker: Mehrdad Moharrami - 2025 Prospective Student Visit Day and Graduate Research Symposium
Title: Recovering Planted Structures in Randomly Weighted Graphs
Abstract:
We study the recovery of hidden structures in randomly weighted graphs, focusing on two canonical cases: the planted matching and the planted spanning tree. In the matching problem, a perfect pairing of vertices is hidden among random edges; we show that when the signal is strong, near-perfect recovery is possible, while weaker signals lead to a sharp threshold where only partial recovery can be achieved. In the spanning tree problem, a hidden spanning tree is embedded in a randomly weighted complete graph. We analyze the performance of the minimum spanning tree algorithm, characterize the fraction of the tree that can be recovered, and extend Frieze's zeta(3) result to this planted setting. Across both problems, our results identify the boundaries between exact recovery, partial recovery, and failure, establishing when efficient algorithms succeed through techniques from probability, graph theory, and combinatorial optimization.
Bio: Moharrami is an Assistant Professor in Computer Science at the University of Iowa. Previously, he was a TRIPODS Postdoctoral Research Fellow at UIUC, working with Prof. R. Srikant. He earned his BSc in Mathematics and Electrical Engineering from the Sharif University of Technology, Iran, and holds MSc degrees in Electrical Engineering and Mathematics from the University of Michigan. In Winter 2020, he received his PhD in Electrical Engineering, earning the Rackham Predoctoral Fellowship for his dissertation.
2025 Prospective Student Visit Day and Graduate Research Symposium details here