5 papers
Bellman-Ford in Almost-Linear Time for Dense Graphs
George Z. Li, Jason Li, Junkai Zhang
We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in time by refining t…
Differentially Private Matchings
Michael Dinitz, George Z. Li, Quanquan C. Liu +1
Computing matchings in graphs is a foundational algorithmic task. Despite extensive interest in differentially private (DP) graph analysis, work on privately computing matching sol…
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…