8 papers · 1 filter
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…
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…
Fine-Grained Privacy Guarantees for Coverage Problems
Laxman Dhulipala, George Z. Li
We introduce a new notion of neighboring databases for coverage problems such as Max Cover and Set Cover under differential privacy. In contrast to the standard privacy notion for…
Near-Optimal Differentially Private k-Core Decomposition
Laxman Dhulipala, George Z. Li, Quanquan C. Liu
Recent work by Dhulipala et al. \cite{DLRSSY22} initiated the study of the -core decomposition problem under differential privacy via a connection between low round/depth distri…
Concentration of Submodular Functions and Read-k Families Under Negative Dependence
Sharmila Duppala, George Z. Li, Juan Luque +2
We study the question of whether submodular functions of random variables satisfying various notions of negative dependence satisfy Chernoff-like concentration inequalities. We pro…