Chengyuan Deng, Rutgers University

Abstract

The hereditary discrepancy of a set system is a quantitative measure of the pseudorandom properties of the system. Roughly speaking, hereditary discrepancy measures how well one can 2-color the elements of the system so that each set contains approximately the same number of elements of each color. In this work, we study the upper and lower bounds on the hereditary discrepancy of set systems of unique shortest paths in graphs. We show that any system of unique shortest paths in an undirected weighted graph has hereditary discrepancy $O(n^{1/4})$, and we construct lower bound examples demonstrating that this bound is tight up to polylog (n) factors, which holds even for planar graphs and bipartite graphs. We also show similar bounds on (non-hereditary) discrepancy in the setting of directed graphs. As applications, we improve the lower bound on the additive error for differentially-private all pairs shortest distances from $Omega(n^{1/6})$ [Chen et al.~SODA 23] to $tilde{Omega}(n^{1/4})$, and we improve the lower bound on additive error for the differentially-private all sets range queries problem to $tilde{Omega}(n^{1/4})$, which is tight up to $polylog (n)$ factors [Deng et al. WADS 23].

See: https://theory.cs.rutgers.edu/theory_seminar