Pith. sign in

REVIEW 3 major objections 5 minor 35 references

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A polynomial-time differentially private algorithm releases a sparse synthetic graph approximating every cut within $1+\gamma$ multiplicative error and $n^{1.25+o(1)}$ additive error, breaking the $n^{1.5}$ barrier.

desk verdict Solid advance breaking the n^1.5 barrier for efficient private cut sparsification via a new private expander decomposition; the main error analysis holds, but the privacy composition for the recursive decomposition needs formal proof before I'd call it fully rigorous. read the letter →

arxiv 2507.01873 v1 pith:2JEJRDO4 submitted 2025-07-02 cs.DS

Anders Aamand , Justin Y. Chen , Mina Dalirrooyfard , Slobodan Mitrović , Yuriy Nevmyvaka , Sandeep Silwal , Yinzhan Xu This is my paper · ORCID
classification cs.DS
keywords differentialprivacygraphsparsificationcutexpanderdecompositionsyntheticqueriesapproximationalgorithmsprivaterelease
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to solve a long-standing gap in differentially private graph release: a polynomial-time algorithm that outputs a sparse synthetic graph approximating all cuts of a large weighted graph, with both a $(1+\gamma)$ multiplicative factor and as little additive error as possible. Prior polynomial-time algorithms were stuck at $O(n^{1.5})$ additive error on dense graphs, while a near-optimal $O(n \log n)$ error was reachable only in exponential time. The authors claim to break the $n^{1.5}$ barrier with an $(\varepsilon,\delta)$-DP algorithm whose additive error is $n^{1.25+o(1)}$ (up to polylog factors in $1/\delta$ and $1/\varepsilon$), while outputting a graph with only $\widetilde{O}(n/\gamma^2)$ edges. The strategy is to privately decompose the graph into dense expander components and a sparse remainder, then use a different private release mechanism on each part, exploiting the fact that the dense parts are so well-connected that their per-vertex additive noise is absorbed by the multiplicative error.

What carries the argument

The load-bearing mechanism is a private expander decomposition (Theorem 3.1). A graph is a $\psi$-expander if every cut $S$ with $|S| \le |V\setminus S|$ has sparsity $\varphi(S)=w_G(S)/|S|$ at least $\psi$; the decomposition partitions $V$ into $V_1,\dots,V_k$ such that each induced subgraph $G[V_i]$ is a $\psi$-expander and the total weight of edges between different parts is $\psi \cdot n^{1+o(1)}$. The algorithm privatizes the recursive expander decomposition of [NS17] by replacing its cut-finding step with a private cut oracle (Theorem 4.2) built from the private graph release of [UUA21] and the deterministic weighted balanced-cut algorithm of [LS21]. Setting $\psi \approx n^{0.5+o(1)}$ makes each component dense enough that the $|C|\sqrt{n}$ additive error of the per-component private release is absorbed into the $\gamma w_G(S)$ multiplicative slack, so only the sparse inter-component edges contribute the $n^{1.25+o(1)}$ additive error, which is bounded using the $\sqrt{W n}$ cut-norm algorithm of [EKKL20].

What would settle it

Run Algorithm 2 on a weighted graph whose edge weights span the allowed $U = O(n^2)$ ratio (for instance, a path with geometrically decreasing weights), on two edge-neighboring inputs, and trace every recursive call whose input graph differs. If a single edge difference ever affects two different recursive calls at the same recursion level, or if the observed recursion depth exceeds $L \cdot c_{\mathrm{size}} \cdot n^\sigma \log n = n^{o(1)}$, the claimed $(\varepsilon,\delta)$-DP composition bound fails.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: for any $\gamma \in (0,1)$, there exists a polynomial-time $(\varepsilon,\delta)$-differentially private algorithm that, given any non-negative weighted $n$-node graph $G=(V,E,w)$, outputs a non-negative weighted graph $H$ with $\widetilde{O}(n/\gamma^2)$ edges such that, with high probability, every cut $S \subseteq V$ satisfies $$|w_G(S)-w_H(S)| \le \gamma w_G(S) + \frac{$n^{{1.25+o(1)}}$ \operatorname{polylog}(1/\delta)}{\varepsilon \$gamma^{{0.5}}$},$$ where $w_G(S)$ is the total weight of edges crossing from $S$ to $V\setminus S$. This breaks the $O(n^{1.5})$ additive error of the best prior polynomial-time private cut sparsifiers, and it does so while keeping the output sparse; the remaining gap to the exponential-time $O(n \log n)$ bound is a factor of $n^{0.25+o(1)}$. The proof constructs a private expander decomposition, applies a cut-norm-based private release to the sparse inter-component edges, and applies a per-vertex-noise private release inside each expander component, where the expander's sparsity guarantee makes the additive noise a constant fraction of every nontrivial cut.

Load-bearing premise

The load-bearing premise is that changing a single edge's weight affects at most one recursive call at each level of the private expander decomposition, so the total privacy loss is at most the recursion depth times the per-call privacy budget; the paper asserts this and the needed recursion-depth bound of [NS17] extends to weighted graphs without providing a formal proof.

Editorial extensions

If this is right

  • The additive error for polynomial-time private cut sparsification drops from $O(n^{1.5})$ to $n^{1.25+o(1)}$ (up to polylog factors in $1/\delta$ and $1/\varepsilon$) for dense graphs, closing roughly a quarter of the gap to the exponential-time $O(n \log n)$ bound.
  • Because the output is a sparse graph with $\widetilde{O}(n/\gamma^2)$ edges, it is suitable for memory- and communication-limited settings where the prior dense synthetic graph was prohibitive.
  • Running standard non-private optimization algorithms on the released synthetic graph yields $(\varepsilon,\delta)$-DP algorithms for Max-Cut, Max-Bisection, Max-k-Cut, and Min-Bisection with the same improved $n^{1.25+o(1)}$ additive error, matching the best known multiplicative approximation ratios.
  • An improved additive-error algorithm for graphs with roughly $n^{1.5}$ edges would, by plugging into this decomposition, automatically improve the bound for all graphs, as the paper notes in its conclusion.
  • The algorithm works for non-negative weighted graphs under edge-neighboring differential privacy, where a neighboring graph's total edge weight differs by at most 1.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same white-box privatization recipe—decompose into dense pieces where crude private release already meets the multiplicative guarantee, privatize the decomposition itself, and handle the sparse remainder separately—could transfer to other non-private decompositions (low-diameter decompositions, dense subgraph covers) for cut-based query release.
  • The practical payoff of this method is largest when the sparse remainder has total weight near its worst-case $n^{1.5+o(1)}$; on sparser inputs the previous $\sqrt{mn}$ additive-error algorithms may still dominate, so a hybrid switch between the two could be the best empirical choice.
  • The privacy proof's reliance on a single-branch-per-level perturbation and on the unproved extension of the recursion-depth lemma to weighted graphs is the part to scrutinize first; a formal coupling argument or an explicit counterexample would settle whether the effective $\varepsilon$ budget is exactly as claimed.
  • Because the released synthetic graph preserves all cuts to $n^{1.25+o(1)}$ additive error, it could serve as a private proxy for downstream tasks such as spectral clustering or densest-subgraph discovery, where cut values are the primary query.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes the first polynomial-time differentially private algorithm for releasing a sparse synthetic graph that approximates all cuts with multiplicative error 1+γ and additive error n^{1.25+o(1)} polylog(1/δ)/(ε γ^{0.5}), breaking the longstanding n^{1.5} additive-error barrier for efficient private cut sparsification. The main technical ingredient is a private expander-decomposition algorithm (Theorem 3.1), obtained by combining a private approximate balanced-cut oracle (Theorem 4.2, built from [UUA21] and [LS21]) with the recursive expander-decomposition framework of [NS17]. The private synthetic graph is then formed by treating inter-component edges and intra-component expanders separately, using [EKKL20] and [UUA21] respectively, and post-processing with a standard non-private cut sparsifier yields the sparse output. The paper also gives applications to private max-cut, max-bisection, max-k-cut, and minimum-bisection with improved additive error.

Significance. If the main theorem holds, this is a substantial advance: it resolves, in a strong sense, the prominent open problem of beating O(n^{1.5}) additive error for polynomial-time private cut sparsification when multiplicative error is allowed. The high-level decomposition into sparse and dense parts is natural and the additive-error accounting in Section 3.3 is clean and correct given the private expander decomposition. The private expander decomposition itself is a potentially reusable primitive. The paper also gives credit where due by building on prior DP algorithms as black boxes. The main weakness is that the privacy proofs for the recursive decomposition are informal at load-bearing points; these need to be made rigorous before the central claim is fully established.

major comments (3)
  1. [Section 3.1] The privacy analysis of Algorithm 1 assumes that the partition V_1,...,V_k produced by Theorem 3.1 is the same for two neighboring graphs. This is not justified: the partition is a randomized, data-dependent output of a private mechanism, and there is no coupling in the text that makes the two partitions coincide. A correct proof needs either an explicit coupling or a composition argument that first releases the partition with its own privacy budget and then argues that, for every fixed partition, the collection of subsequent invocations of Theorem 2.2 is private under parallel composition. As written, the claim that 'at most three invocations' consume privacy budget does not establish (ε,δ)-DP for Algorithm 1, because the adversary observes which subproblems are created and those subproblems depend on the private partition.
  2. [Section 4, privacy proof of Algorithm 2] The argument 'when Algorithm 2 recurses, the edge e affects at most one of the recursive calls' is a statement about a single execution. In a privacy proof, the recursive subproblems A(H,ψ) are themselves outputs of private computations, so the set of subproblems and their vertex sets can differ between neighboring graphs. The text then concludes that Algorithm 2 is (ε,δ)-DP by basic composition over at most D = L·c_size·n^σ·log n affected calls, but all n^{1+o(1)} recursive-call outputs are released. A formal composition theorem for data-dependent recursive partitioning is needed; simply multiplying the per-call privacy budget by the depth bound is not basic composition. Since this is the step that transfers privacy from the per-call oracle to Theorem 3.1, the current proof leaves the central privacy guarantee unsupported.
  3. [Section 4, Lemma 4.4 and Lemma 4.3] Lemmas 4.3 and 4.4 are imported from [NS17], which is stated for unweighted graphs, and are asserted to extend to arbitrary non-negative weighted graphs 'with little to no change of their proofs'. This is load-bearing: Lemma 4.4 supplies the recursion-depth bound D that sets the privacy budget ε' = ε/(L·c_size·n^σ·log n), and if the weighted version fails then the privacy guarantee collapses. The second bullet of Lemma 4.3 also requires a weighted version of the inter-component edge-count bound. The paper should either prove these extensions in full or give a precise derivation showing exactly which parts of the [NS17] argument carry over to arbitrary non-negative weights; a citation to an unweighted statement is insufficient for the claimed weighted theorem.
minor comments (5)
  1. [Section 3.3, Eq. (3)] The equality |w_{\tilde G_i}(C_i)-w_{G_i}(C_i)| - α w_{G_i}(C_i) = |w_{\tilde G_i}(D_i)-w_{G_i}(D_i)| - α w_{G_i}(D_i) uses the fact that w(C_i)=w(D_i); this should be stated explicitly for clarity.
  2. [Table 1 and Theorem 1.1] The notation for the multiplicative approximation parameter is inconsistent: Table 1 uses α while the theorem statements use γ. Please align the notation.
  3. [Theorem 4.2] The theorem statement refers to parameters cexp and csize before they are defined; define them directly in the statement or immediately before it.
  4. [Corollary 5.2] The runtime claim 'poly(n, log log(1/δ), log(1/ε))' for the Max-k-Cut algorithm appears unrelated to the rest of the paper and is likely a typo; please state the actual polynomial runtime.
  5. [Section 4, Algorithm 2] The definition of σ = sqrt(log cexp / log n) is used only in the privacy budget and depth bound; it would help to state explicitly that L = O(1/σ) and to spell out the resulting no(1) bound.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central claim reduces to external black-box results, not to the paper's own outputs or fitted parameters.

full rationale

Walking the derivation chain: Theorem 1.1 follows from Theorem 3.2 by post-processing with [BK96]; Theorem 3.2 composes Theorem 3.1 with external private algorithms [UUA21] and [EKKL20]; Theorem 3.1 is obtained by instantiating Algorithm 2 with Theorem 4.2, whose correctness is a post-processing argument over [UUA21], and whose recursive-structure lemmas (Lemmas 4.3 and 4.4) are imported from the external [NS17] paper. The only self-citations ([ACD+24], [DMN23]) occur in related-work comparisons and are not load-bearing. The parameters psi, alpha, and the per-call privacy budget epsilon' = epsilon/(L csize n^sigma log n) are chosen analytically to make inequalities (2) and (3) hold; they are not fitted to data, and no quantity presented as predicted is defined in terms of the output. The paper's own Appendix A only converts [EKKL20]'s expected cut-norm bound into a high-probability bound via repetition, which is independent of the main theorem. There is a genuine rigor concern in Section 4: the privacy argument assumes the recursive partition is the same across neighboring graphs and asserts, without proof, that the [NS17] recursion-depth bound extends to weighted graphs. This is a correctness risk, not a circularity, because those facts are imported from external work and do not presuppose the paper's conclusions.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim rests on black-box results from prior work and on an asserted extension of [NS17]'s lemmas to weighted graphs. No new physical or mathematical entities are introduced.

free parameters (1)
  • sparsity threshold ψ = n^{0.5+o(1)} polylog(1/δ)/(αε)
    Chosen to balance the additive error from the sparse inter-component edges against the multiplicative error from the dense expander pieces (Section 3, Algorithm 1, step 2). Any value above Ψ(n) works, so it is an analytic tradeoff parameter rather than a fitted constant.
assumptions (4)
  • domain assumption Theorem 2.2 ([UUA21]) provides a polynomial-time (ε,δ)-DP algorithm with per-cut error O(|S| sqrt(n) polylog(n/δ)/ε).
    Used as a black box in Algorithm 1 and in the private sparse-cut subroutine (Theorem 4.2). The paper relies on its stated guarantees without proof.
  • domain assumption Theorem 2.3 ([EKKL20]) provides a polynomial-time (ε,δ)-DP algorithm with cut-norm error O(sqrt(w(E)n/ε) polylog(n/δ)).
    Used to privatize the sparse inter-component edges. The paper proves a high-probability version in Appendix A but relies on the original result.
  • domain assumption Theorem 4.1 ([LS21], Theorem 2.14) gives a deterministic weighted expander decomposition finder with bicriteria approximation (d_exp, d_size).
    Used in Theorem 4.2 as the post-processing subroutine. The paper cites it directly.
  • ad hoc to paper The structural lemmas of the [NS17] expander decomposition (Lemma 4.3: sparsity and inter-component edge weight bound; Lemma 4.4: recursion depth) extend to weighted graphs with 'little to no change of their proofs'.
    The paper asserts this extension without a proof. The central error bound and the privacy composition both depend on these lemmas.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition." pith.science (2026). https://pith.science/paper/2JEJRDO4

@misc{pith2026250701873,
  author       = {Pith},
  title        = {Pith review of: Breaking the $n^1.5$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2JEJRDO4}},
  note         = {Machine review of arXiv:2507.01873}
}
abstract

We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been made, the best-known private and efficient cut sparsifiers on $n$-node graphs approximate each cut within $\widetilde{O}(n^{1.5})$ additive error and $1+\gamma$ multiplicative error for any $\gamma > 0$ [Gupta, Roth, Ullman TCC'12]. In contrast, "inefficient" algorithms, i.e., those requiring exponential time, can achieve an $\widetilde{O}(n)$ additive error and $1+\gamma$ multiplicative error [Eli{\'a}{\v{s}}, Kapralov, Kulkarni, Lee SODA'20]. In this work, we break the $n^{1.5}$ additive error barrier for private and efficient cut sparsification. We present an $(\varepsilon,\delta)$-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error $1+\gamma$ and additive error $n^{1.25 + o(1)}$ (ignoring dependencies on $\varepsilon, \delta, \gamma$). At the heart of our approach lies a private algorithm for expander decomposition, a popular and powerful technique in (non-private) graph algorithms.

Figures

Figures reproduced from arXiv: 2507.01873 by the authors.

Figure 1
Figure 1. For ψ = n 0.5+o(1), our algorithm privately obtains a partition of the vertices of G into sets V1, . . . , Vk such that (1) each induced subgraph G[Vi ] (red) has sparsity at least ψ and (2) the total weight of edges between components (blue) is ψ · n 1+o(1). We run the Oe( √ nm) additive error algorithm by [EKKL20] on Esparse formed by the blue edges, and the algorithm by [UUA21] on each G[Vi ]. The high density of… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 29 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Better balance by being biased: A 0.8776-approximation for max bisection

    Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Better balance by being biased: A 0.8776-approximation for max bisection. ACM Transactions on Algorithms (TALG) , 13(1):1--27, 2016

    2016

  3. [3]

    Differentially Private Gomory-Hu Trees

    Anders Aamand, Justin Y Chen, Mina Dalirrooyfard, Slobodan Mitrovi \'c , Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu. Differentially private Gomory-Hu trees. arXiv preprint arXiv:2408.01798 , 2024

    work page Pith review arXiv 2024

  4. [4]

    Approximating the cut-norm via grothendieck's inequality

    Noga Alon and Assaf Naor. Approximating the cut-norm via grothendieck's inequality. SIAM J. Comput. , 35(4):787--803, 2006

    work page 2006

  5. [5]

    On differentially private graph sparsification and applications

    Raman Arora and Jalaj Upadhyay. On differentially private graph sparsification and applications. In Proceedings of the Advances in Neural Information Processing Systems 32 (NeurIPS) , pages 13378--13389, 2019

    work page 2019

  6. [6]

    Wherefore art thou R3579X? anonymized social networks, hidden patterns, and structural steganography

    Lars Backstrom, Cynthia Dwork, and Jon Kleinberg. Wherefore art thou R3579X? anonymized social networks, hidden patterns, and structural steganography. In Proceedings of the 16th international conference on World Wide Web (WWW) , pages 181--190, 2007

    work page 2007

  7. [7]

    Bencz\' u r and David R

    Andr\' a s A. Bencz\' u r and David R. Karger. Approximating s - t minimum cuts in O (n^2) time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , STOC '96, page 47–55. Association for Computing Machinery, 1996

    work page 1996

  8. [8]

    Differentially private multiway and k -cut

    Rishi Chandra, Michael Dinitz, Chenglin Fan, and Zongrui Zou. Differentially private multiway and k -cut. CoRR , abs/2407.06911, 2024

    arXiv 2024

Show all 35 references
  1. [9]

    A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond

    Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pages...

    2020

  2. [10]

    Chris Culnane, Benjamin I. P. Rubinstein, and Vanessa Teague. Stop the open data bus, we want to get off. CoRR , abs/1908.05004, 2019

    1908 arXiv

  3. [11]

    On approximate graph colouring and max-k-cut algorithms based on the -function

    Etienne de Klerk, Dmitrii V Pasechnik, and Joost P Warners. On approximate graph colouring and max-k-cut algorithms based on the -function. Journal of Combinatorial Optimization , 8:267--294, 2004

    2004

  4. [12]

    Differential privacy and robust statistics

    Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC) , pages 371--380, 2009

    2009

  5. [13]

    Nearly tight bounds for differentially private multiway cut

    Mina Dalirrooyfard, Slobodan Mitrovi \'c , and Yuriy Nevmyvaka. Nearly tight bounds for differentially private multiway cut. In Proceedings of the Advances in Neural Information Processing Systems 36 (NeurIPS) , 2023

    2023

  6. [14]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Conference (TCC) , volume 3876, pages 265--284, 2006

    2006

  7. [15]

    Differential privacy

    Cynthia Dwork. Differential privacy. In Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming (ICALP) , pages 1--12, 2006

    2006

  8. [16]

    Differentially private release of synthetic graphs

    Marek Eli \'a s , Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 560--578, 2020

    2020

  9. [17]

    Improved approximation algorithms for MAX k -CUT and MAX BISECTION

    Alan Frieze and Mark Jerrum. Improved approximation algorithms for MAX k -CUT and MAX BISECTION . Algorithmica , 18(1):67--81, 1997

    1997

  10. [18]

    On graph problems in a semi-streaming model

    Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science , 348(2-3):207--216, 2005

    2005

  11. [19]

    Garey, David S

    Michael R. Garey, David S. Johnson, and Larry Stockmeyer. Some simplified NP -complete problems. In Proceedings of the sixth annual ACM symposium on Theory of computing , pages 47--63, 1974

    1974

  12. [20]

    Differentially private combinatorial optimization

    Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2010

    2010

  13. [21]

    Anupam Gupta, Aaron Roth, and Jonathan R. Ullman. Iterative constructions and private data release. In Proceedings of the 9th Theory of Cryptography Conference (TCC) , volume 7194, pages 339--356, 2012

    2012

  14. [22]

    Goemans and David P

    Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM) , 42(6):1115--1145, 1995

    1995

  15. [23]

    Accurate estimation of the degree distribution of private networks

    Michael Hay, Chao Li, Gerome Miklau, and David Jensen. Accurate estimation of the degree distribution of private networks. In 2009 Ninth IEEE International Conference on Data Mining , pages 169--178. IEEE, 2009

    2009

  16. [24]

    Random sampling in cut, flow, and network design problems

    David R Karger. Random sampling in cut, flow, and network design problems. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing , pages 648--657, 1994

    1994

  17. [25]

    Optimal inapproximability results for MAX-CUT and other 2-variable CSP s? SIAM Journal on Computing , 37(1):319--357, 2007

    Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSP s? SIAM Journal on Computing , 37(1):319--357, 2007

    2007

  18. [26]

    Private graph data release: A survey

    Yang Li, Michael Purcell, Thierry Rakotoarivelo, David Smith, Thilina Ranbaduge, and Kee Siong Ng. Private graph data release: A survey. ACM Computing Surveys , 55(11):1--39, 2023

    2023

  19. [27]

    Deterministic weighted expander decomposition in almost-linear time

    Jason Li and Thatchaphol Saranurak. Deterministic weighted expander decomposition in almost-linear time. CoRR , abs/2106.01567, 2021

    2021 arXiv

  20. [28]

    Optimal bounds on private graph approximation

    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, 2024

    2024

  21. [29]

    Robust de-anonymization of large sparse datasets

    Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In Proceedings of the 2008 IEEE Symposium on Security and Privacy (SP) , pages 111--125, 2008

    2008

  22. [30]

    Dynamic spanning forest with worst-case update time: adaptive, Las Vegas , and O(n\( ^ 1/2 - \( \) \)) -time

    Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, Las Vegas , and O(n\( ^ 1/2 - \( \) \)) -time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23...

    2017

  23. [31]

    Optimal hierarchical decompositions for congestion minimization in networks

    Harald R \"a cke. Optimal hierarchical decompositions for congestion minimization in networks. In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 255--264, 2008

    2008

  24. [32]

    Approximating CSP s with global cardinality constraints using SDP hierarchies

    Prasad Raghavendra and Ning Tan. Approximating CSP s with global cardinality constraints using SDP hierarchies. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages 373--387. SIAM, 2012

    2012

  25. [33]

    Expander decomposition and pruning: Faster, stronger, and simpler

    Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2616--2635, 2019

    2019

  26. [34]

    Differentially private analysis on graph streams

    Jalaj Upadhyay, Sarvagya Upadhyay, and Raman Arora. Differentially private analysis on graph streams. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021 , volume 130 of Proceedings of Machine Learning Research , pages 1171--1179. PMLR , 2021

    2021

  27. [35]

    Fully-dynamic minimum spanning forest with improved worst-case update time

    Christian Wulff - Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages 1130--1143, 2017

    2017

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.