Differentially Private Matchings

Computing matchings in general graphs plays a central role in graph algorithms. However, despite the recent interest in differentially private graph algorithms, there has been limited work on private matchings. Almost all existing work focuses on estimating the size of the maximum matching, whereas in many applications, the matching itself is the object of interest. There is currently only a single work on private algorithms for computing matching solutions by [HHRRW STOC'14]. Moreover, their work focuses on allocation problems and hence is limited to bipartite graphs. In this talk, we give a number of new results in the domain of differentially private matchings with algorithms drawing inspiration from fast algorithms in distributed computing. 

Joint work with Michael Dinitz, George Z. Li, and Felix Zhou.