4 papers · 1 filter
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Laxman Dhulipala, Monika Henzinger, George Z. Li +3
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k…
Paths and Intersections: Exact Emulators for Planar Graphs
George Z. Li, Zihan Tan, Tianyi Zhang
We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with terminals, the goal is to construct an emulator, which is a s…
On Differential Privacy for Adaptively Solving Search Problems via Sketching
Shiyuan Feng, Ying Feng, George Z. Li +3
Recently differential privacy has been used for a number of streaming, data structure, and dynamic graph problems as a means of hiding the internal randomness of the data structure…
Edge-Private Matching Kernels Through Local Decoding
Michael Dinitz, George Z. Li, Quanquan C. Liu +1
A matching is a set of edges with no shared endpoints. We study how participants can retain useful matching structure when each knows its own relationships but those relationships…