George Z. Li
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
George Z. Li has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Jason Li
Carnegie Mellon University
2 shared publications - David P. Woodruff
Carnegie Mellon University, Pittsburgh, USA
1 shared publication Henry Fleischmann
Carnegie Mellon University {hfleisch
1 shared publication- Junkai Zhang
Tsinghua University
1 shared publication - Lichen Zhang
Boston University
1 shared publication Shiyuan Feng
1 shared publication
Latest Publications
- Open Access
Bellman-Ford in Almost-Linear Time for Dense Graphs
We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in $n^{2+o(1)}$ time by refining the shortcutting procedure introduced in Li, Li, Rao, and Zhang (2026).Open AccessBellman-Ford in Almost-Linear Time for Dense Graphs
We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in $n^{2+o(1)}$ time by refining the shortcutting procedure introduced in Li, Li, Rao, and Zhang (2026). - Open Access
Faster Weak Expander Decompositions and Approximate Max Flow
We give faster algorithms for weak expander decompositions and approximate max flow on undirected graphs. First, we show that it is possible to "warm start" the cut-matching game when computing weak expander decompositions, avoiding the cost of the recursion depth. Our algorithm is also flexible enough to support weaker flow subroutines than previous algorithms. Our second contribution is to streamline the recent non-recursive approximate max flow algorithm of Li, Rao, and Wang (SODA, 2025) and adapt their framework to use our new weak expander decomposition primitive. Consequently, we give an approximate max flow algorithm within a few logarithmic factors of the limit of expander decomposition-based approaches.
Open AccessFaster Weak Expander Decompositions and Approximate Max Flow
We give faster algorithms for weak expander decompositions and approximate max flow on undirected graphs. First, we show that it is possible to "warm start" the cut-matching game when computing weak expander decompositions, avoiding the cost of the recursion depth. Our algorithm is also flexible enough to support weaker flow subroutines than previous algorithms. Our second contribution is to streamline the recent non-recursive approximate max flow algorithm of Li, Rao, and Wang (SODA, 2025) and adapt their framework to use our new weak expander decomposition primitive. Consequently, we give an approximate max flow algorithm within a few logarithmic factors of the limit of expander decomposition-based approaches.
- Open Access
On Differential Privacy for Adaptively Solving Search Problems via Sketching
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, so that multiple possibly adaptive queries can be made without sacrificing the correctness of the responses. Although these works use differential privacy to show that for some problems it is possible to tolerate $T$ queries using $\widetilde{O}(\sqrt{T})$ copies of a data structure, such results only apply to numerical estimation problems, and only return the cost of an optimization problem rather than the solution itself. In this paper, we investigate the use of differential privacy for adaptive queries to search problems, which are significantly more challenging since the responses to queries can reveal much more about the internal randomness than a single numerical query. We focus on two classical search problems: nearest neighbor queries and regression with arbitrary turnstile updates. We identify key parameters to these problems, such as the number of $c$-approximate near neighbors and the matrix condition number, and use different differential privacy techniques to design algorithms returning the solution vector with memory and time depending on these parameters. We give algorithms for each of these problems that achieve similar tradeoffs.Open AccessOn Differential Privacy for Adaptively Solving Search Problems via Sketching
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, so that multiple possibly adaptive queries can be made without sacrificing the correctness of the responses. Although these works use differential privacy to show that for some problems it is possible to tolerate $T$ queries using $\widetilde{O}(\sqrt{T})$ copies of a data structure, such results only apply to numerical estimation problems, and only return the cost of an optimization problem rather than the solution itself. In this paper, we investigate the use of differential privacy for adaptive queries to search problems, which are significantly more challenging since the responses to queries can reveal much more about the internal randomness than a single numerical query. We focus on two classical search problems: nearest neighbor queries and regression with arbitrary turnstile updates. We identify key parameters to these problems, such as the number of $c$-approximate near neighbors and the matrix condition number, and use different differential privacy techniques to design algorithms returning the solution vector with memory and time depending on these parameters. We give algorithms for each of these problems that achieve similar tradeoffs.