The analysis of graph data is fundamental to modern machine learning,as it provides a framework for extracting insights from interconnected
entities. However, graphs often contain sensitive information (such as in social networks), and thus ensuring privacy in graph algorithms is
critically important.
In this talk, we present several graph algorithms developed under differential privacy, a leading framework that offers rigorous
mathematical guarantees for privacy protection. We will cover algorithms for privately releasing graph statistics, such as all-pair
distances, spectral properties, and all-cut sizes, as well as algorithms for privately approximating combinatorial structures like
max-cut, min k-cut, and multiway cut.

Moreover, this talk also explores how the privatization techniques underlying these algorithms connect to broader topics in theoretical computer science, including
computational phase transitions and MCMC sampling.

Zongrui Zou is a fourth-year Ph.D. student in the Department of Computer Science at Nanjing University, China. His research interests
lie broadly in theoretical computer science, with a primary focus on establishing mathematical guarantees for privacy-preserving algorithms
and exploring their applications in machine learning and combinatorial optimization. His research work has been published in premier venues
across both theoretical computer science and machine learning, including FOCS, SODA, ICLR, and NeurIPS etc.