报告题目：Partitioning a Special Class of Cayley Graphs with Spectral Approximation

报告人：张鹏教授，Rutgers University

报告时间：2024年11月11日（周一）9:00-10:00

报告地点：20-200

报告摘要：Given a graph G = (V, E), we want to partition the edge set of G into E_1 and E_2 such that each of the two edge-induced subgraphs G_1 = (V, E_1) and G_2 = (V, E_2) spectrally approximates (1/2)G with a relative error O(\sqrt{\alpha}) (in terms of spectral norms of graph Laplacians), where \alpha is the maximum effective resistance between any two endpoints of an edge in G. A well-known result of Marcus, Spielman, and Srivastava implies the above edge partition always exists, but no polynomial-time algorithms are known. We explore polynomial-time algorithms for partitioning a special class of Cayley graphs of Z_n whose generators form an arithmetic progression. Our algorithm relies on partitioning the generators of a Cayley graph. Furthermore, we show if the generators are far from an arithmetic progression, there is no partition of the generators that yields two Cayley subgraphs with an error matching O(\sqrt{\alpha}).

个人简介：Peng Zhang is an assistant professor in the Department of Computer Science at Rutgers University. Peng is broadly interested in algorithms, data science, and causal inference. Her work has been recognized with an NSF CAREER Award, an Adobe Data Science Research Award, and a FOCS Best Student Paper award. Before joining Rutgers, she received her Ph.D. in Computer Science from Georgia Tech and worked as a postdoc at Yale University.