betaFeedback

WorksComputer Science

Differentially Private All-Pairs Min Cut Values

Abstract

We study the problem of privately releasing the min cut values of all pairs of vertices in a given nn-node weighted graph, under the edge-neighboring model. Straightforward application of advanced composition yields an approximate DP algorithm that outputs all min cut values up to O~(n)\tilde{O}(n) additive error. Prior works [Dalirrooyfard, Mitrovi{ć} and Nevmyvaka, 2023; Aamand et al., 2026] have established that Θ~(n)\tildeΘ(n) is the correct bound if the algorithm also needs to output cuts that realize the approximate min cut values. On the other hand, simply outputting the values could be an easier problem, but prior algorithms have been stuck on the O~(n)\tilde{O}(n) bound. In this work, we give an approximate DP algorithm outputting all-pair min cut values with O~(n)\tilde{O}(\sqrt{n}) additive error, beating the linear error barrier. Our algorithm applies the sparse vector technique [Dwork and Roth, 2014] to maintain a hierarchical decomposition of the vertices based on the min cut structure. We also prove an Ω(log⁡3/2n)Ω(\log^{3/2} n) lower bound for this problem.

Introduction

Given a weighted graph7 G=(V,E,w)G=(V,E,w), a vertex partition (S,V∖S)(S,V\setminus S) is called a cut, and the sum of weights of the edges with one endpoint in SS and another endpoint in V∖SV\setminus S is called the value of that cut. Recently, there has been increasing interest in understanding cut problems in the context of differential privacy, including global min cut [12], min ss-tt cut [6 CDFZ26], all-pairs min ss-tt cuts [2], cut sparsifier [13, 10, 15, 1], and more [14, 6 CDFZ26]. In these works and also in our paper, the model of neighboring datasets is edge-neighboring: two neighboring graphs are those whose total edge weights differ by at most one, and in a single edge.

We consider one of the simplest problems: min ss-tt cut. This problem admits an interesting behavior depending on what exactly we wish to output. For a fixed pair (s,t)(s,t), it is known how to output an entire ss-tt cut8 with an ϵ\epsilon-DP algorithm, whose cut value in the underlying graph differs by O~(n/ϵ)\widetilde{O}(n/\epsilon) from the actual min ss-tt cut [6]. The O~(n)\widetilde{O}(n) additive error bound is also known to be tight [6]. Interestingly, the same O~(n/ϵ)\widetilde{O}(n/\epsilon) bound can be achieved even if one needs to privately output an approximate min ss-tt cut for every pair s,t∈Vs,t\in V [2].

On the other hand, if the goal is instead to output the (approximate) cut values, one can potentially do much better. For example, to output a single min ss-tt cut value privately, we only need to naively add Lap⁡(1/ϵ)\operatorname{Lap}(1/\epsilon) noise to the true min ss-tt cut value, resulting in O(1/ϵ)O(1/\epsilon) additive error (in expectation), which is much smaller than the O~(n/ϵ)\widetilde{O}(n/\epsilon) bound. However, it seems more challenging to output the values of all min ss-tt cut with lower additive error than privately releasing the cuts themselves. Namely, since there are n2n^2 values to output, we can apply advanced composition to achieve additive error O~(n)\widetilde{O}(n) (with approximate DP), which matches the error bound of [2], but is significantly weaker since the algorithm in [2] is able to output the cuts themselves. This has prompted [2] to raise the natural open question of whether there is an algorithm that releases all-pairs min-cut values with error polynomially smaller than O~(n)\widetilde{O}(n); the distinction between releasing cuts and releasing only their values has also been noted in [6 CDFZ26].

In this work, we answer this open question in the affirmative, and show how to output all min ss-tt cut values with quadratically lower additive error than outputting the cuts themselves.

Theorem 1.1. Let ϵ,δ,β>0\epsilon,\delta,\beta>0. There exists an (ϵ,δ)(\epsilon,\delta)-DP algorithm which for any non-negatively weighted nn vertex graph G=(V,E,w)G=(V,E,w) outputs values λ~(s,t)\widetilde{\lambda}(s,t) for each s,t∈Vs,t\in V. If the value of the ss-tt min-cut in GG is λ(s,t)\lambda(s,t), then with probability at least 1−β1-\beta it holds simultaneously over all s,t∈Vs,t\in V that

∣λ~(s,t)−λ(s,t)∣=O(nlog⁡(1/δ)ϵ(log⁡n+log⁡(1/β))).\left|\widetilde{\lambda}(s,t)-\lambda(s,t)\right|=O\left(\frac{\sqrt{n\log(1/\delta)}}{\epsilon}\left(\log n+\log(1/\beta)\right)\right).

We also give a (much weaker) lower bound, showing that releasing all min ss-tt cut values is quantitatively harder than releasing a single min-cut value: Corollary 4.1 shows that, for a natural range of ϵ\epsilon and δ\delta, every (ϵ,δ)(\epsilon,\delta)-DP mechanism which outputs all cut values from a fixed source node ss must incur additive error Ω(log⁡3/2nmax⁡{ϵ,δ})\Omega\left(\frac{\log^{3/2}n}{\max\{\epsilon,\delta\}}\right) on some cut value. In contrast, prior works of [6, 2] show that both tasks are equally efficient (both have Θ~ϵ,δ(n)\widetilde{\Theta}_{\epsilon,\delta}(n) additive error), if one is also required to release cuts certifying the min-cut values. Notably, our lower bound holds for an easier problem since we fix one end point.

Open Problems. Given the exponential gap between our upper and lower bounds, a natural open problem is to improve the bounds in either direction towards discovering the asymptotically optimal bounds. It is also interesting to ask for improved bounds for the problem of releasing all min ss-tt cut values for a fixed public node ss, the “single-source” version of the problem studied in this work. For this simpler problem, naively applying advanced composition already gives O~ε,δ(n)\widetilde{O}_{\varepsilon,\delta}(\sqrt{n}) dependence, and we ask if this bound can be improved.

Preliminaries

Let G=(V,E,w)G=(V,E,w) be a weighted graph, where we throughout this paper assume that E=(V2)E=\binom{V}{2}; we interpret edges of weight zero as non-edges. For u,v∈Vu,v\in V, we use λG(u,v)\lambda_G(u,v) to denote the value of a min cut between uu and vv in the graph GG. We recall some basic DP definitions.

Definition 2.1 (Edge-Neighboring Graphs). Graphs G=(V,E,w)G=(V,E,w) and G′=(V,E,w′)G'=(V,E,w') are called edge-neighboring if there is e∈Ee\in E such that ∣w(e)−w′(e)∣≤1\lvert w(e)-w'(e)\rvert\le1 and for all e′∈E∖{e}e'\in E\setminus\{e\}, w(e′)=w′(e′)w(e')=w'(e').

Definition 2.2 (Differential Privacy [9]). A randomized algorithm A\mathcal{A} is (ε,δ)(\varepsilon,\delta)-DP if for any neighboring graphs GG and G′G' and any set of possible outcomes OO of A\mathcal{A} it holds P[A(G)∈O]≤eεP[A(G′)∈O]+δ\mathbb{P}[\mathcal{A}(G)\in O]\le e^\varepsilon\mathbb{P}[\mathcal{A}(G')\in O]+\delta. When δ=0\delta=0, algorithm A\mathcal{A} is called pure DP, or ε\varepsilon-DP.

Now we describe the version of the sparse vector technique (SVT) that we require for our main algorithm for releasing all pairwise min-cut values under differential privacy. Let X\mathcal{X} be an input space equipped with a neighboring relation ∼\sim. For a scalar query q:X→Rq:\mathcal{X}\to\mathbb{R}, define its global ℓ1\ell_1-sensitivity by

Δ(q):=sup⁡x,x′∈X,x∼x′∣q(x)−q(x′)∣.\Delta(q):=\sup_{\substack{x,x'\in\mathcal{X},\,x\sim x'}}\lvert q(x)-q(x')\rvert.

Adaptive threshold queries. We employ an adaptive version of SVT that allows us to approximately answer a sequence of questions of the form “Is qi(x)≥Tiq_i(x)\ge T_i?” for a sequence of scalar queries q1,…,qKq_1,\ldots,q_K each of ℓ1\ell_1 sensitivity at most Δ\Delta and a sequence of thresholds T1,…,TKT_1,\ldots,T_K. Adaptivity means that the algorithm can choose qiq_i and TiT_i based on answers to previous questions. At round ii, after observing the preceding transcript hi−1∈{Yes,No}i−1h_{i-1}\in\{\mathrm{Yes},\mathrm{No}\}^{i-1}, the algorithm chooses a new query qi:X→Rq_i:\mathcal{X}\to\mathbb{R} and a threshold Ti∈RT_i\in\mathbb{R}. SVT roughly states that we are able to get accurate answers up to additive error scaling with ≈c\approx\sqrt{c}, where cc is the total number of Yes answers we will get.

Theorem 2.1 (SVT). Consider any ε∈(0,1)\varepsilon\in(0,1), δ,Δ,β>0\delta,\Delta,\beta>0, and c∈Nc\in\mathbb{N}. Consider a private dataset DD and a sequence q1,…,qkq_1,\ldots,q_k of (adaptively chosen) sensitivity $\Delta queries along with a sequence of thresholds T1,…,TkT_1,\ldots,T_k. Let

α=16Δ2cln⁡(1/δ)(log⁡k+log⁡(2c/β))ε\alpha=\frac{16\Delta\sqrt{2c\ln(1/\delta)}(\log k+\log(2c/\beta))}{\varepsilon}

There exists an (ε,δ)(\varepsilon,\delta)-DP algorithm which outputs a sequence a1,…,aka_1,\ldots,a_k with ai∈{Yes,No,Halt}∗suchthatthefollowingholdswithprobability∗$1−βa_i\in\{\mathrm{Yes},\mathrm{No},\mathrm{Halt}\} *such that the following holds with probability* \$1-\beta across all timesteps i∈{1,…,k}i\in\{1,\ldots,k\}

  • If ai=Yesa_i=\mathrm{Yes}, then qi(D)≥Ti−αq_i(D)\ge T_i-\alpha.

  • If ai=Noa_i=\mathrm{No}, then qi(D)≤Ti+αq_i(D)\le T_i+\alpha.

  • If ai=Halta_i = \mathrm{Halt}, then ∣{aj:j<i and aj=Yes}∣=c|\{a_j : j < i \text{ and } a_j = \mathrm{Yes}\}| = c (the algorithm has already answered Yes cc times).

This version of the SVT theorem which we use slightly differs from a standard presentation in [8] though follows immediately from the same techniques, we defer its proof to Section A.

Algorithm for DP All-Pairs Min-Cut Values

In this section we prove Theorem 1.1. For simplicity, we first assume that for the graph G=(V,E,w)G = (V, E, w), ww is bounded by a polynomial in nn. At the end of the section, we discuss how to handle arbitrary non-negative edge weight. We start with the following observation.

Observation 3.1. Let s,t,vs, t, v be three arbitrary vertices in the graph, and T≥0T \ge0 be a real number. If λG(s,t)≥T\lambda_G(s,t) \ge T and λG(s,v)≥T\lambda_G(s,v) \ge T, then λG(t,v)≥T\lambda_G(t,v) \ge T as well.

Proof. Suppose λG(t,v)\lambda_G(t,v) is T′<TT' < T. Consider the two components of a Min-tt-vv-Cut: AtA_t and AvA_v. If s∈Ats \in A_t, then (At,Av)(A_t,A_v) is an ss-vv-Cut as well, and so λG(s,v)\lambda_G(s,v) is at most T′<TT' < T, a contradiction. Similarly, if s∈Avs \in A_v, then (At,Av)(A_t,A_v) is a ss-tt-Cut as well and so λG(s,t)\lambda_G(s,t) is at most T′<TT' < T, a contradiction. So λG(t,v)\lambda_G(t,v) must be at least TT. □

As in Theorem 2.1, we define

α=162nln⁡(1/δ)(log⁡k+log⁡(2n/β))ε.\alpha= \frac{16\sqrt{2n\ln(1/\delta)}(\log k + \log(2n/\beta))}{\varepsilon}.

Here, kk is an upper bound on the number of SVT scalar queries our algorithm will make. We later upper-bound kk by nO(1)n^{O(1)}. In particular, Theorem 2.1 guarantees that under (ε,δ)(\varepsilon,\delta)-DP, with probability at least 1−β1-\beta, we can answer up to kk scalar queries of sensitivity at most one within error α\alpha as long as the number of Yes answers is at most nn. Our scalar functions are of the form qC1,C2q_{C_1,C_2} for disjoint subsets C1,C2⊂VC_1,C_2 \subset V where

qC1,C2(G)=max⁡u∈C1,v∈C2λG(u,v).q_{C_1,C_2}(G) = \max_{u\in C_1,v\in C_2} \lambda_G(u,v).

Clearly qC1,C2q_{C_1,C_2} has sensitivity at most one under the notion of edge-neighboring graphs.

Our algorithm consists of poly⁡(n)\operatorname{poly}(n) many steps each with a different cut threshold. At each step ii with threshold TiT_i, the vertices will be decomposed into components, such that if ss and tt are in the same component, λG(s,t)\lambda_G(s,t) is at least Ti−αT_i-\alpha, and if they are in different components, λG(s,t)\lambda_G(s,t) is smaller than Ti+αT_i+\alpha. At step i+1i+1, we lower the threshold and coarsen this decomposition.

At step 00 we start with a high threshold T0T_0 such that the λG(s,t)<T0−α\lambda_G(s,t) < T_0-\alpha for all s,t∈Vs,t \in V and having all components be singletons. By the assumption that the edge weights are polynomially bounded, it suffices to set T0=poly⁡(n)T_0 = \operatorname{poly}(n). Going from step ii to step i+1i+1, we let Ti+1=Ti−αT_{i+1} = T_i-\alpha.

Suppose at the beginning of step ii, we have tit_i components C1,…,CtiC_1,\ldots,C_{t_i}. We take two arbitrary components Cj,Cj′C_j,C_{j'} and query if qCj,Cj′(G)q_{C_j,C_{j'}}(G) is at least TiT_i. If the answer is Yes, we merge CjC_j and Cj′C_{j'}. We continue until we coarsen the decomposition to ti+1≤tit_{i+1} \le t_i many components where for each pair of current components C,C′C,C' we have performed the above threshold query qC,C′(G)q_{C,C'}(G) with answer No.

Lemma 3.1. At step ii, we perform O(ti2)O(t_i^2) queries. If the number of Yes queries during step ii is yiy_i, then ti+1=ti−yit_{i+1}=t_i-y_i, i.e. the number of components at step i+1i+1 is the number of components at step ii minus the number of YES queries.

Proof. During step ii, two components can merge at most ti−1t_i-1 times, so there are at most 2ti−12t_i-1 distinct components in total that can ever be part of a query, including the tit_i initial components and the components created by merging. Since each pair of components is queried at most once during step ii, the total number of queries during step ii is at most (2ti−12)=O(ti2)\binom{2t_i-1}{2}=O(t_i^2). Each time we get a YES, the number of components goes down by one which proves the second statement. □

Corollary 3.1. The total number of Yes queries the algorithm asks is at most n−1n-1 and the total number of queries is poly⁡(n)\operatorname{poly}(n).

Proof. The first statement follows directly from the previous lemma, and the second statement follows since we assumed the weights of GG and hence T0T_0 is polynomially bounded. □

The next lemma shows that we can approximately recover the values of the min-cuts from the steps ii at which components merged.

Lemma 3.2. With probability at least 1−β1-\beta, the following holds simultaneously for every step i≥1i\ge1: if CC and C′C' are two components that merge at step ii, then, for every s∈Cs\in C and t∈C′t\in C', λG(s,t)\lambda_G(s,t) is in [Ti−α,Ti−1+α][T_i-\alpha,T_{i-1}+\alpha].

Proof. Let E\mathcal{E} be the event that all threshold queries are answered within error α\alpha. Since the total number of Yes queries is at most n−1n-1 by Corollary 3.1, it follows from Theorem 2.1 and the way we set α\alpha that P[E]≥1−β\mathbb{P}[\mathcal{E}]\ge1-\beta. It thus suffices to show that if E\mathcal{E} occurs, λG(s,t)\lambda_G(s,t) is in [Ti−α,Ti−1+α][T_i-\alpha,T_{i-1}+\alpha] deterministically. We use induction on ii. For i=0i=0, there is nothing to prove. However, note that since all min-cuts in the graph are smaller than T0−αT_0-\alpha, under E\mathcal{E}, no components are merged during step i=0i=0. Assume that i>0i>0 and that the result holds for smaller values of ii.

We first prove the upper bound. Let C0C_0 and C0′C'_0 be the components containing ss and tt, respectively, at the end of step i−1i-1. Since C0C_0 and C0′C'_0 did not merge during step i−1i-1, the query qC0,C0′q_{C_0,C'_0} with threshold Ti−1T_{i-1} was answered with No. Under E\mathcal{E}, this implies that for every pair of nodes u∈C0u\in C_0 and v∈C0′v\in C'_0, λG(u,v)≤Ti−1+α\lambda_G(u,v)\le T_{i-1}+\alpha, and in particular λG(s,t)≤Ti−1+α\lambda_G(s,t)\le T_{i-1}+\alpha.

It remains to prove that λG(s,t)≥Ti−α\lambda_G(s,t)\ge T_i-\alpha. We prove that, throughout step ii, any two vertices in the same component have min-cut value at least Ti−αT_i-\alpha. This holds at the beginning of step ii by the induction hypothesis and the fact that the thresholds are decreasing. Now suppose that CC and C′C' were merged during step ii. Under E\mathcal{E}, this implies that qC,C′(G)≥Ti−αq_{C,C'}(G)\ge T_i-\alpha since the query was answered with a Yes. Consequently, there exist u∈Cu\in C and v∈C′v\in C' such that λ(u,v)≥Ti−α\lambda(u,v)\ge T_i-\alpha. Inductively, all pairs of vertices within CC, and all pairs within C′C', have min-cut values at least Ti−αT_i-\alpha. Since having min-cut at least Ti−αT_i-\alpha is an equivalence relation by Observation 3.1, it follows that λG(s,t)≥Ti−α\lambda_G(s,t)\ge T_i-\alpha, as desired. □

We can now prove our main result

Proof of Theorem 1.1. We run the algorithm described above. As weights are nonnegative, when ii is large enough that Ti−1≤−αT_{i-1}\le-\alpha, ti=1t_i=1 with probability at least 1−β1-\beta, so there is just one component on all nn nodes left. For any pair of nodes s,ts,t, we note the step ii in which the components of ss and tt are merged and our estimate of λG(s,t)\lambda_G(s,t) is simply TiT_i. By Lemma 3.2, with probability at least 1−β1-\beta, the error is

∣Ti−λG(s,t)∣≤2α.\lvert T_i-\lambda_G(s,t)\rvert\le2\alpha.

Using Corollary 3.1, the number of queries kk is polynomial in nn, so it follows that the error 2α2\alpha is bounded by

O(nlog⁡(1/δ)ε(log⁡n+log⁡(1/β))).O\left(\frac{\sqrt{n\log(1/\delta)}}{\varepsilon}(\log n+\log(1/\beta))\right).

The algorithm is (ε,δ)(\varepsilon,\delta)-DP as the merge history and hence the estimates are post-processing of the (ε,δ)(\varepsilon,\delta)-DP SVT answers.

Handling Unbounded Weights. While we proved our result for polynomially bounded weight functions, there is a simple trick to obtain an algorithm with no such assumption. The idea is to use half the privacy budget to first obtain coarse estimates of all pairwise min-cut values. This can be done by adding independent Laplace noise Lap⁡(2/ε)\operatorname{Lap}(2/\varepsilon) to each edge weight of GG and computing the min-cut values on the resulting graph. With probability at least 1−β/21-\beta/2, no edge changes weight by more than O(log⁡(n/β)/ε)O(\log(n/\beta)/\varepsilon), so all cut values are preserved within O(n2log⁡(n/β)/ε)O(n^2\log(n/\beta)/\varepsilon).

We use the second half of the privacy budget to simulate the algorithm behind Theorem 1.1. However, since we have coarse bounds on the min-cut values, instead of running the threshold queries for every step ii, we only need to consider steps ii such that TiT_i is within O(n2log⁡(n/β)/ε+α)O(n^2\log(n/\beta)/\varepsilon+\alpha) of some min-cut value of the graph. Since there are at most n−1n-1 different min-cut values in any non-negatively weighted graph [11], the number of steps ii we need to consider is therefore

O((n−1)⋅n2log⁡(n/β)/ε+αα)=O(n3log⁡(n/β)αε+n)=O(n5/2log⁡(1/δ)+n)=O(n5/2).O\left((n-1)\cdot\frac{n^2\log(n/\beta)/\varepsilon+\alpha}{\alpha}\right) =O\left(\frac{n^3\log(n/\beta)}{\alpha\varepsilon}+n\right) =O\left(\frac{n^{5/2}}{\sqrt{\log(1/\delta)}}+n\right) =O(n^{5/2}).

and the number of queries kk is at most a polynomial factor in nn larger. We thus obtain that log⁡k=O(log⁡n)\log k=O(\log n). Setting the failure probability of the second algorithm to β/2\beta/2, a union bound gives that the final algorithm fails with probability at most β\beta, and the final error remains unchanged within constant factors.

A Lower Bound for Releasing All-Pairs Min-Cut Values

In this section, we prove an Ωε,δ(log⁡3/2n)\Omega_{\varepsilon,\delta}(\log^{3/2} n) error lower bound for releasing all-pairs min-cut values. The lower bound holds for an easier problem of releasing all the min-cut values from a single fixed source. The main idea is a reduction from the well studied problem of releasing prefix sums, which is classical in differential privacy [7, 5]. We recall its definition below.

Definition 4.1 (DP Prefix-Sum Problem). For a string x=(x1,…,xd)∈{0,1}dx=(x_1,\ldots,x_d)\in\{0,1\}^d and k∈[d]k\in[d], define its prefix sums as pk(x)=∑j=1kxjp_k(x)=\sum_{j=1}^{k}x_j. Two strings xx and x′x' are called neighboring if they differ in exactly one coordinate. The DP prefix-sum problem asks to output all the values p1(x),…,pd(x)p_1(x),\ldots,p_d(x) under this neighboring definition.

A recent work proves the following lower bound [3]. Importantly for our setting, their lower bound holds even in the offline model, in which the mechanism receives the entire string before producing its output.

Theorem 4.1 ([3]). There is a sufficiently small constant C>0C > 0 such that, for any

d−1+Ω(1)<ε<1and0<δ<C,d^{-1+\Omega(1)} < \varepsilon< 1 \qquad\text{and}\qquad0 < \delta< C,

every (ε,δ)(\varepsilon,\delta)-DP mechanism A:{0,1}d→RdA:\{0,1\}^{d}\to\mathbb{R}^{d} for the offline prefix-sum problem satisfies

max⁡x∈{0,1}dE[∥A(x)−(p1(x),…,pd(x))∥∞]=Ω(log⁡3/2dmax⁡{ε,δ}).\max_{x\in\{0,1\}^{d}}\mathbb{E}\left[\left\|A(x)-(p_1(x),\ldots,p_d(x))\right\|_{\infty}\right] = \Omega\left(\frac{\log^{3/2}d}{\max\{\varepsilon,\delta\}}\right).

Remark: Here, the condition d−1+Ω(1)<εd^{-1+\Omega(1)} < \varepsilon means that ε≥d−1+γ\varepsilon\ge d^{-1+\gamma} for some fixed constant γ>0\gamma> 0. The implicit constant in the lower bound may depend on γ\gamma.

We now give a reduction from the problem of Definition 4.1 to releasing all min-cut values from a single fixed source. The main idea in the lemma is to encode prefix sums as min cuts from a single source node, using a modified path graph; we refer to Figure 1.

Figure 1. Example of the lower bound gadget.

Lemma 4.1. For every x∈{0,1}dx\in\{0,1\}^{d}, there is a simple undirected weighted graph GxG_x on d+2d+2 vertices, with a source ss and vertices v0,…,vdv_0,\ldots,v_d, such that

λGx(s,vk−1)=d+1+pk(x)for every k∈[d].(1)\lambda_{G_x}(s,v_{k-1}) = d+1+p_k(x) \qquad\text{for every } k\in[d]. \tag*{(1)}

If xx and x′x' differ in one coordinate, then GxG_x and Gx′G_{x'} differ in the weight of one edge by 1.

Proof. Given a string x∈{0,1}dx\in\{0,1\}^{d}, we construct the corresponding graph GxG_x as follows. This is also shown in Figure 1. Let the vertices be v0,v1,…,vd+1v_0,v_1,\ldots,v_{d+1} and set the source as s=vd+1s=v_{d+1}. First connect the vertices viv_i in a path with all edge weights W:=d+1W:=d+1. That is, for each i∈[d+1]i\in[d+1], add the path edge ei={vi−1,vi}e_i=\{v_{i-1},v_i\} with weight WW. This is independent of the string xx. Now to incorporate the string, for each j∈[d]j\in[d], add the edge {vj−1,s}\{v_{j-1},s\} with weight xjx_j. For example, when d=4d=4, the construction is shown in Figure 1.

It is clear that for two neighboring strings x,x′x,x' in the sense of Definition 4.1, their corresponding graphs differ in exactly one edge by weight one.

Now the important claim is that the min cuts from the source ss are exactly the prefix sums of the string xx, up to an additive shift WW which is known. Indeed, consider the min-cut between ss and node viv_i for some i≤d−1i\le d-1. Let’s imagine the vertices as linearly ordered as shown in Figure 1. Due to our choice of WW, we never want to cut more than one weight-WW edge and it is clear that at least one weight-WW edge must be cut. It is also clear that a weight-WW edge after viv_i must be cut, otherwise there is a path of weight-WW edges from viv_i to ss. If we cut some weight-WW edge adjacent to vi′v_{i'} for i′≥ii'\ge i, then we must also cut all the edges corresponding to x1,…,xi′+1x_1,\ldots,x_{i'+1} (otherwise there is a path from ss to viv_i), and these additional edges we cut incur cost which is equal to the prefix sum pi′+1(x)p_{i'+1}(x). But since prefix sums are non-decreasing, it never hurts to take i′=ii'=i, in which case we get the prefix sum pi+1(x)p_{i+1}(x), and shifting the index by 1 proves (1).

Consequently, any (ε,δ)(\varepsilon,\delta)-DP mechanism for releasing all min-cut values of GxG_x from the source ss gives an (ε,δ)(\varepsilon,\delta)-DP mechanism for releasing all prefix sums of xx. Indeed, if we have min cut estimates λ~(s,vk−1)\widetilde{\lambda}(s,v_{k-1}), we output the prefix sum estimate λ~(s,vk−1)−(d+1)\widetilde{\lambda}(s,v_{k-1})-(d+1). This reduction preserves both differential privacy and additive ℓ∞\ell_\infty error. This observation along with the reduction of Lemma 4.1 and the prior result of Theorem 4.1 immediately proves the following corollary.

Corollary 4.1. There is a sufficiently small constant C>0C>0 such that, for any n−1+Ω(1)<ε<1n^{-1+\Omega(1)}<\varepsilon<1 and 0<δ<C0<\delta<C, every (ε,δ)(\varepsilon,\delta)-DP mechanism that, on an nn-vertex simple undirected weighted graph with a fixed public source ss, releases estimates λ~G(s,v)\widetilde{\lambda}_G(s,v) for every v≠sv\ne s must satisfy

max⁡GE[max⁡v∈V(G)∖{s}∣λ~G(s,v)−λG(s,v)∣]=Ω(log⁡3/2nmax⁡{ε,δ}).\max_G \mathbb{E}\left[\max_{v\in V(G)\setminus\{s\}}\left|\widetilde{\lambda}_G(s,v)-\lambda_G(s,v)\right|\right]=\Omega\left(\frac{\log^{3/2}n}{\max\{\varepsilon,\delta\}}\right).

There are several interesting remarks to make. The first is that the lower bound holds for the easier problem of releasing all min cut values from a single fixed source, rather than APMC values. It is an interesting question to determine if this is the right answer for the fixed source problem. The second is that the result shows a separation between releasing one fixed min cut value and releasing APMC values. For a single min cut, one can obtain expected error O(1/ε)O(1/\varepsilon) using the Laplace mechanism, whereas APMC values requires error that must grow with the number of vertices. Lastly, the lower bound shows that APMC is a “harder” problem than privately releasing all vertex degrees of a graph (which are perhaps the most natural overestimates of the true min cut values), since degrees can be released with Oε(log⁡n)O_\varepsilon(\log n) error.

Declaration of AI Use

The lower bound of Corollary 4.1 was derived by ChatGPT 5.6 Pro when the authors prompted it with a prior weaker lower bound based on the packing argument. The writing was heavily edited by the authors and the authors assume responsibility for all content.

Proof of SVT Theorem

We give a proof of a slightly non-standard utility theorem for the Sparse Vector Technique (SVT). This follows immediately from standard analysis found in [8] but is not precisely the theorem stated there. For completeness, we include the proof here.

Background from [8]. Consider the AboveThreshold algorithm (Algorithm 1 in [8]), which takes in a private dataset DD, a privacy parameter ε\varepsilon, a sequence f1,…,fkf_1,\ldots,f_k of (adaptively chosen) sensitivity 1 queries, and a threshold TT. After receiving each query, the algorithm either outputs No and continues to the next query or outputs Yes and halts, it answers no more queries after this point. Let aia_i be the output after receiving query fif_i. In Theorem 3.23 of their work, the authors prove that this algorithm (ε,0)(\varepsilon,0)-DP.

Lemma A.1. AboveThreshold is (ε,0)(\varepsilon,0)-DP.

Within the proof of Theorem 3.25 of their work (which is not exactly what we want), the authors use the Laplace tail bound and a union bound to show the following statement.

Lemma A.2. Let

α=8(log⁡k+log⁡(2/β))ε.\alpha= \frac{8(\log k+\log(2/\beta))}{\varepsilon}.

Then, with probability β\beta, the following holds across all timesteps:

  • If ai=Yesa_i=\mathrm{Yes}, then fi(D)≥T−αf_i(D)\ge T-\alpha.

  • If ai=Noa_i=\mathrm{No}, then fi(D)≤T+αf_i(D)\le T+\alpha.

Finally, for our proof, we need the advanced composition theorem, appearing as Corollary 3.21 in their work.

Theorem A.1. For all ε∈(0,1)\varepsilon\in(0,1) and δ>0\delta>0, kk-fold adaptive composition of (ε′,0)(\varepsilon',0)-DP mechanisms satisfies (ε,δ)(\varepsilon,\delta)-DP as long as

ε′≤ε22kln⁡(1/δ).\varepsilon' \le\frac{\varepsilon}{2\sqrt{2k\ln(1/\delta)}}.

Now, we are ready to prove the version of SVT theorem we use.

Theorem 2.1 (SVT). Consider any ε∈(0,1)\varepsilon\in(0,1), δ,Δ,β>0\delta,\Delta,\beta>0, and c∈Nc\in\mathbb{N}. Consider a private dataset DD and a sequence q1,…,qkq_1,\ldots,q_k of (adaptively chosen) sensitivity Δ\Delta queries along with a sequence of thresholds T1,…,TkT_1,\ldots,T_k. Let

α=16Δ2cln⁡(1/δ)(log⁡k+log⁡(2c/β))ε.\alpha= \frac{16\Delta\sqrt{2c\ln(1/\delta)}(\log k+\log(2c/\beta))}{\varepsilon}.

There exists an (ε,δ)(\varepsilon,\delta)-DP algorithm which outputs a sequence a1,…,aka_1,\ldots,a_k with ai∈{Yes,No,Halt}a_i\in\{\mathrm{Yes},\mathrm{No},\mathrm{Halt}\} such that the following holds with probability 1−β1-\beta across all timesteps i∈{1,…,k}i\in\{1,\ldots,k\}

  • If ai=Yesa_i=\mathrm{Yes}, then qi(D)≥Ti−αq_i(D)\ge T_i-\alpha.

  • If ai=Noa_i=\mathrm{No}, then qi(D)≤Ti+αq_i(D)\le T_i+\alpha.

  • If ai=Halta_i = \mathrm{Halt}, then ∣{aj:j<i and aj=Yes}∣=c\lvert\{a_j : j < i \text{ and } a_j = \mathrm{Yes}\}\rvert= c (the algorithm has already answered Yes cc times).

Proof. We implement SVT by composition of at most cc calls to AboveThreshold. We normalize and recenter all queries qiq_i for SVT to fi=(qi−Ti)/Δf_i = (q_i - T_i)/\Delta for AboveThreshold with a fixed threshold T=0T = 0. When a call to AboveThreshold returns No, SVT will return No. When a call to AboveThreshold returns Yes and halts, SVT will return Yes and instantiate a fresh call to AboveThreshold if the number of Yes outputs is less than cc. Otherwise, SVT will return Halt for the remainder of time.

Let ε′=ε22cln⁡(1/δ)\varepsilon' = \frac{\varepsilon}{2\sqrt{2c\ln(1/\delta)}}. Note that SVT’s only interaction with the private dataset DD is via the outputs of at most cc instantiations of AboveThreshold. Using ε′\varepsilon' as the privacy parameter for each call to AboveThreshold, SVT is (ε,δ)(\varepsilon,\delta)-DP by Lemma A.1 and Theorem A.1.

The utility of SVT follows from that of AboveThreshold via Lemma A.2 plugging in ε′\varepsilon' and β′=β/c\beta' = \beta/c in order to union bound over the failure probability of each call to AboveThreshold. Lemma A.2 gives additive error

α=8(log⁡k+log⁡(2/β′))ε′=16(log⁡k+log⁡(2c/β))2cln⁡(1/δ)ε.\alpha= \frac{8(\log k + \log(2/\beta'))}{\varepsilon'} = \frac{16(\log k + \log(2c/\beta))\sqrt{2c\ln(1/\delta)}}{\varepsilon}.

Since AboveThreshold operates on the normalized queries fi=qi/Δf_i = q_i/\Delta, the additive error term in the final theorem statement has an additional factor Δ\Delta.

References

  1. [1]Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu. Breaking the n^{1.5} additive error barrier for private and efficient graph sparsification via private expander decomposition. In Forty-second International Conference on Machine Learning, 2025. ↑2arxiv.org/abs/2507.01873
  2. [2]Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu. Differentially private gomory-hu trees. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. ↑2arxiv.org/abs/2408.01798
  3. [3]Konstantina Bairaktari and Kasper Green Larsen. The binary tree mechanism is optimal for approximate differentially private continual counting. arXiv preprint arXiv:2607.00876, 2026. ↑6, ↑7arxiv.org/abs/2607.00876
  4. [5]T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1–24, 2011. ↑6
  5. [6]Mina Dalirrooyfard, Slobodan Mitrović, and Yuriy Nevmyvaka. Nearly tight bounds for differentially private multiway cut. Advances in Neural Information Processing Systems, 36:24947–24965, 2023. ↑2DOI
  6. [7]Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715–724, 2010. ↑6DOI
  7. [8]Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014. ↑4, ↑10
  8. [9]Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pages 1–12. Springer, 2006. ↑3
  9. [10]Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 560–578. SIAM, 2020. ↑2
  10. [11]Ralph E Gomory and Tien Chung Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961. ↑6DOI
  11. [12]Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1106–1125. SIAM, 2010. ↑2
  12. [13]Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of cryptography conference, pages 339–356. Springer, 2012. ↑2
  13. [14]Justin Hsu, Aaron Roth, Tim Roughgarden, and Jonathan Ullman. Privately solving linear programs. In International Colloquium on Automata, Languages, and Programming, pages 612–624. Springer, 2014. ↑2DOI
  14. [15]Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph approximation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1019–1049. SIAM, 2024. ↑2arxiv.org/abs/2309.17330

Paper details

vlnc:W_868b4xag
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 5.6 Pro

View statement
Looking for related papers…
Contents