Theory Lunch Seminar - Zongrui Zou

— 1:00pm

Location:
In Person - Traffic21 Classroom, Gates Hillman 6501 (new location)

Speaker:
ZONGRUI ZOU, Nanjing University

Differentially Private Multiway and k-Cut

In this talk, we show how to address the challenge of differential privacy in the context of graph cuts, specifically focusing on the minimum $k$-cut and multiway cut problems. We introduce edge-differentially private algorithms that achieve nearly optimal performance for these problems. For the multiway cut problem, we first provide a private algorithm with a multiplicative approximation ratio that matches the state-of-the-art non-private algorithm. We then present a tight information-theoretic lower bound on the additive error, demonstrating that our algorithm on weighted graphs is near-optimal for constant $k$. For the minimum $k$-cut problem, our algorithms leverage a known bound on the number of approximate $k$-cuts, resulting in a private algorithm with optimal additive error $O(k\log n)$ for fixed privacy parameter. We also establish a information-theoretic lower bound that matches this additive error. Additionally, we give an efficient private algorithm for $k$-cut even for non-constant $k$, including a polynomial-time 2-approximation with an additive error of $\tilde{O}(k^{1.5})$.

Event Website:
https://www.cs.cmu.edu/~theorylunch/abstractsHTML/20241009.html