Differentially Private Graph Coloring

Aravind Srinivasan; Dung Nguyen; Jiayi Wu; Michael Xie

REVIEW 2 major objections 1 minor 20 references

Differentially Private Graph Coloring

T0 review · 2 major / 1 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read This paper shows that edge-differentially private vertex coloring can be done with about Δ/log n colors, at the cost of allowing each vertex to share its color with O(log n/ε) neighbors.

desk verdict The paper has a genuinely new algorithmic template, but the central DP claims are not supported as written: a sign error flips the utility bound, Algorithm 2's threshold uses the true max degree, and the trivial uniform-random-coloring baseline already matches the stated guarantees. read the letter →

arxiv 2602.13460 v2 pith:5F4SYW7K submitted 2026-02-13 cs.DS

Michael Xie , Jiayi Wu , Dung Nguyen , Aravind Srinivasan This is my paper · ORCID

classification cs.DS MSC 05C1568P2768W20

keywords differentialprivacygraphcoloringdefectiveedgeexponentialmechanismd-inductivegraphsrandomizedalgorithms

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 tackles releasing a vertex coloring of a graph whose edges are sensitive. It argues that any nontrivial edge-differentially private coloring must be defective, because a proper coloring would instantly reveal which pairs of vertices are not connected. Two algorithms are presented: the first, for d-inductive graphs, is 3ε-differentially private with O(log n/ε + d) maximum defectiveness; the second, for all graphs, is 5ε-differentially private with O(log n/ε) maximum defectiveness, both using Θ(Δ/log n + 1/ε) colors. The core idea is a uniformly random initial coloring followed by exponential-mechanism resampling of colors, with the second algorithm resampling only vertices whose noisy defectiveness exceeds a threshold. If the privacy claims hold, these are the first topology-adaptive defective colorings under edge differential privacy.

What carries the argument

The exponential mechanism with defectiveness score s(v,k) = number of neighbors of v already colored k, whose global sensitivity is 1; in Algorithm 2, a noisy threshold on each vertex's defectiveness decides whether to resample that vertex. The initial uniform coloring makes the expected number of same-colored neighbors about Δ/C = log n, so bad events are rare; the exponential mechanism then biases recoloring toward colors with fewer same-colored neighbors while the sensitivity-1 score keeps privacy loss small.

What would settle it

Take two graphs G and G' that differ by a single edge but whose maximum degrees differ by 1, and a vertex v whose noisy defectiveness is near Algorithm 2's threshold; because the threshold itself changes, the ratio Pr[q(v)=1 in G] / Pr[q(v)=1 in G'] can exceed e^ε, contradicting the claimed 5ε privacy. Alternatively, for Algorithm 1, fix two neighboring graphs with different d-inductive orderings and compute the ratio of output probabilities for a given coloring; the vertex permutation in the product does not cancel, and the ratio grows with n, exceeding e^{3ε}.

Watch

Extended reading notes

Core claim

The central discovery is that defective coloring — where each vertex may share its color with up to k neighbors — is the right utility target for edge-differentially private graph coloring, and a two-stage randomization can control defectiveness without blowing up the palette. Starting from a uniform random coloring over C = Θ(Δ/log n + 1/ε) colors, the exponential mechanism resamples colors with scores equal to the number of neighbors already holding that color. Because the score function has sensitivity 1, each resampling step changes the output distribution by only a bounded factor between neighboring graphs, and composition yields 3ε or 5ε privacy. The defectiveness bounds follow from Ch

Load-bearing premise

The privacy guarantees assume the vertex ordering and the resampling threshold are public and fixed, while the utility guarantees require them to depend on the private edge set; if they do, the privacy proofs' cancellation arguments collapse.

Editorial extensions

If this is right

Proper colorings are impossible under edge differential privacy; any released coloring must be defective.
Algorithm 1 provides a 3ε-differentially private coloring with O(log n/ε + d) maximum defectiveness on d-inductive graphs using Θ(Δ/log n + 1/ε) colors.
Algorithm 2 extends the guarantee to all graphs with 5ε differential privacy and O(log n/ε) maximum defectiveness at the same palette size.
The privacy–defectiveness tradeoff is tunable through ε, offering a practical lever for applications that need stronger privacy.
The palette size is Θ(Δ/log n + 1/ε), which for dense graphs is substantially smaller than Δ.

Reading between the lines

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

Algorithm 1's utility proof requires a d-inductive ordering that depends on the private edge set, but its privacy proof treats the ordering as public and fixed; if the ordering is chosen from the data, the cancellation argument in Theorem 3.1 breaks, and a repair would be to publish a fixed ordering or add noise to its selection.
Algorithm 2's resampling threshold uses the private maximum degree Δ directly; replacing it with the same noisy estimate used for the palette would close this gap, but the paper does not do so.
The two-stage recipe — random initialization plus sensitivity-1 exponential-mechanism resampling — may extend to other vertex-labeling problems where imperfect labels are acceptable, such as private community detection or private clustering.

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.

Desk Editor's Note

read the letter

Two things to know. The iterative exponential-mechanism resampling and the controlled-resampling selection are genuinely new algorithmic ideas for edge-DP graph coloring. But the main theorems do not hold as written: Lemma 3.2 has a sign error, and Algorithm 2's threshold is computed from the true max degree, not the privately released one, so the 5ε-DP claim is unsupported. The paper also never compares against the uniform-random-coloring baseline, which already gives O(log n) defect with ε-DP and a noised max degree; that makes the claimed advance over prior work unclear.

What's good: the constructions are new and the paper clearly states a small-ε limitation in Remark 1. The experiments cover both average and max defectiveness on SNAP and synthetic graphs and include a comparison to an existing private coloring algorithm (CRSV), which is more than many theory papers do.

The soft spots are substantial. In the proof of Lemma 3.2, the exponent in the bound should be (Δ/C − k)ε/2, not (k − Δ/C)ε/2. The algebra is off by a sign, and that sign is load-bearing for Theorem 3.3. Fixing it might salvage the utility claim, but the paper needs to be rewritten.

Algorithm 2 uses the true Δ in the threshold T on line 4; Δ is private, so T has sensitivity up to 1. The proof of Theorem 3.4 treats T as fixed and only analyzes changes in the noisy defect counts. That doesn't work. For a graph that is a matching versus one that is a matching plus one edge, T changes by about 4.6, which already saturates the e^{5ε} budget for ε=1. Using Δ̃ instead of Δ in T would fix this, but that's not what the paper does.

Algorithm 1's privacy proof assumes a fixed vertex ordering, but the utility claim relies on a d-inductive ordering that depends on the private graph. That mismatch is unaddressed.

Finally, the experiments don't include the trivial baseline: release Δ̃, then color every vertex uniformly from a palette of size Θ(Δ̃/log n). That mechanism is ε-DP and has max defectiveness O(log n) with high probability, matching the paper's asymptotic guarantees. Without that comparator, the reported improvements over CRSV don't demonstrate that the new algorithms are actually advancing the state of the art.

Who is this for? Researchers working on DP graph algorithms might find the resampling template worth thinking about, and the experimental methodology is a useful data point. But the theoretical core needs serious repair before the results can be trusted. I would not send this to a referee in its current form; it needs a corrected version with a privacy-aware threshold and a fair baseline comparison first.

Referee Report

2 major / 1 minor

Summary. The paper proposes two edge-differentially private vertex-coloring algorithms. Algorithm 1 starts from a uniform random coloring on a palette of size C = Δ̃/log n and resamples every vertex once with the exponential mechanism; it claims 3ε-DP and O(log n/ε + d) maximum defectiveness on d-inductive graphs. Algorithm 2 adds a noisy threshold test to resample only vertices whose noisy defectiveness exceeds a threshold, claiming 5ε-DP and O(log n/ε) maximum defectiveness for all graphs. The authors also report experiments on SNAP and synthetic graphs comparing with the CRSV baseline and a non-private greedy coloring.

Significance. If the two main theorems were correct, the paper would give the first topology-adaptive defective colorings under edge differential privacy, with palette size Θ(Δ/log n + 1/ε) and defect O(log n/ε + d) or O(log n/ε). The high-level idea—using a random initial coloring followed by exponential-mechanism resampling, with a Chernoff-derived threshold for selective resampling—is reasonable and the experiments are described in good faith. However, the privacy and utility proofs contain concrete errors: a sign error in Lemma 3.2, an unprivatized dependence on the true maximum degree in Algorithm 2, and an ordering assumption in Algorithm 1 that is incompatible with the stated utility guarantee. As written, neither the 3ε-DP claim for Algorithm 1 nor the 5ε-DP claim for Algorithm 2 is established. The theoretical contribution is therefore not currently supported.

major comments (2)

[§3.1, Theorem 3.1 vs. Theorem 3.3] The privacy proof of Algorithm 1 assumes the vertex order in line 5 is the same for neighboring graphs, but the utility proof requires sampling in the reverse of a d-inductive ordering, which is a function of the private edge set. For neighboring G and G′, the d-inductive order can differ, so the cancellation of the product over i in Theorem 3.1 is invalid; the probability of the ordering itself is not bounded. Thus 3ε-DP is not established for the algorithm that has the claimed utility. The paper needs either a public ordering (which would destroy the d-dependence of the defect bound) or a private ordering mechanism with a sensitivity analysis; neither is provided.
[§3.2, Algorithm 2 line 12 and Theorem 3.4] Line 12 samples with probability proportional to exp(−ε s(v,k)), whereas the exponential mechanism in Definition 2.2 (and Algorithm 1) uses exp(ε u/(2Δu)). Since the sensitivity of s is 1, the mechanism in line 12 is 2ε-DP, not ε-DP, under the paper’s own definition. The text says Algorithm 2 applies “the same Exponential mechanism as Algorithm 1,” which is false; the exponent differs by a factor of 2. This affects the privacy composition in Theorem 3.4 and also the utility bound in Theorem 3.6, which uses the standard 2Δu/ε gap. The composition count should be redone; with the corrected accounting the total may still be below 5ε, but the proof as written is internally inconsistent.

minor comments (1)

[Throughout] There are frequent typographical issues (e.g., “5epsilon-differently private,” “differently private” in Theorem 3.4, inconsistent use of c for both a color and the palette size, and missing punctuation). A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the privacy and utility derivations are self-contained, with thresholds derived from Chernoff bounds and Laplace/exponential-mechanism sensitivity; the only ad hoc scaling appears in experiments and is not load-bearing.

full rationale

I walked the derivation chain for both algorithms. Algorithm 1: the palette size is set from a Laplace-noised max degree; the defectiveness bound follows from a Chernoff bound on the random initial coloring and an exponential-mechanism utility bound with score sensitivity 1. Algorithm 2: the recoloring threshold is obtained by inverting the Chernoff bound (Equation 1) and adding a Laplace tail term; the defectiveness theorem then composes the threshold event, the exponential mechanism's utility guarantee, and a Poisson bound on recoloring neighbors. None of these steps defines the predicted quantity (defectiveness) in terms of itself, and no fitted parameter is renamed as a prediction. The experimental scaling of the threshold by 0.25 is an explicit tuning choice and is not used in any theorem; it affects the empirical match but does not constitute a circular derivation. References [5] and [6] are external prior works and are not used as load-bearing self-citations. The most serious concerns in the manuscript are correctness/privacy issues, not circularity: Algorithm 2's threshold T in line 4 is a deterministic function of the true max degree Δ, which has sensitivity 1 between neighboring graphs, and the privacy proof treats T as fixed; similarly, Algorithm 1's utility proof relies on a d-inductive ordering that may depend on the private edge set. These are potential flaws in the DP argument but they are not cases where a result is equivalent to its input by construction. Therefore the circularity score is 0.

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

The algorithms introduce no new physical or mathematical entities; they rely on standard DP mechanisms. The main unstated free choices are the data-dependent d-inductive ordering in Algorithm 1 and the experimental threshold scaling. The palette-size formula is not clamped when the noisy max degree is small, and the additive 1/epsilon in the abstract is not reflected in the pseudocode.

free parameters (1)

experimental threshold scale = 0.25
Section 4.1 states 'We also scaled our theoretical threshold of 2 by a factor of 0.25'; this hand-set constant changes utility, although not the claimed privacy guarantee.

assumptions (4)

standard math The Laplace mechanism releases a noisy max degree and this accounts for all privacy loss from using the palette size C = Delta~/log n.
Used in Algorithm 1 step 1 and in Theorem 3.1; however, the proof does not fully handle the data-dependent palette size in the output space.
ad hoc to paper A d-inductive ordering can be used internally by Algorithm 1 without additional privacy loss.
The utility analysis requires processing vertices in reverse d-inductive order, but the privacy proof treats the ordering as fixed; no argument is given for edge-neighboring graphs with different orderings.
standard math Chernoff bound, Laplace mechanism, and exponential mechanism utility guarantees are valid as cited.
Invoked in Section 2 and throughout the proofs of Lemma 3.5 and Theorem 3.6.
domain assumption Edge differential privacy with public vertex set is the relevant privacy model.
Definition 2.8 and problem statement.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Differentially Private Graph Coloring." pith.science (2026). https://pith.science/paper/5F4SYW7K

@misc{pith2026260213460,
  author       = {Pith},
  title        = {Pith review of: Differentially Private Graph Coloring},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5F4SYW7K}},
  note         = {Machine review of arXiv:2602.13460}
}

abstract

Differential Privacy is the gold standard in privacy-preserving data analysis. This paper addresses the challenge of computing an edge-differentially private vertex coloring. In this paper, we present two novel algorithms for this problem. Both algorithms begin by coloring each vertex uniformly at random from a fixed-size palette, and then apply the exponential mechanism to locally resample colors for either all vertices or a selected subset of vertices. Any non-trivial edge differentially private coloring of a graph needs to be defective, as a proper coloring exposes the non-existence of an edge between two vertices of the same color. A coloring is $k$-defective if each vertex shares its color with at most $k$ of its neighbors. Our goal is to design coloring algorithms that use the minimum number of colors, while achieving the smallest possible defect under the edge-differential privacy. Our first algorithm applies to $d$-inductive graphs with maximum degree $\Delta$. We show that it yields a $3\epsilon$-differentially private coloring with $O(\frac{\log n}{\epsilon}+d)$ maximum defect, using a palette of size $\Theta(\frac{\Delta}{\log n}+\frac{1}{\epsilon})$. Our second algorithm utilizes noisy thresholding to guarantee $O(\frac{\log n}{\epsilon})$ maximum defect, using a palette of size $\Theta(\frac{\Delta}{\log n}+\frac{1}{\epsilon})$, generalizing the results to all graphs rather than just $d$-inductive ones.

Figures

Figures reproduced from arXiv: 2602.13460 by the authors.

**Figure 1.** Average defectiveness as a function of ϵ on SNAP networks. 4.2 Experimental results On the SNAP networks, we observe that for Algorithm 1, the average defectiveness exhibits higher variance with smaller ϵ, as our algorithm assigns higher probability mass to options with lower scores in this regime, allowing higher entropy ( [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

**Figure 2.** Maximum defectiveness as a function of ϵ on SNAP networks. the threshold by a constant factor, also increases the number of vertices that recolor. 5 Conclusion In this paper, we proposed two novel edge-differentially private graph coloring algorithms. Both algorithms use O( ∆ log n ) colors. Algorithm 1 achieves a maximum defectiveness of O(log n+d) d-inductive graphs, while Algorithm 2 attains a more general bound … view at source ↗

**Figure 3.** Average (top) and maximum (bottom) defectiveness as a function of [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Average (top) and maximum (bottom) defectiveness as a function of [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 2 linked inside Pith

[1]

Statistical mechanics of complex networks.Reviews of modern physics, 74(1):47, 2002

R´ eka Albert and Albert-L´ aszl´ o Barab´ asi. Statistical mechanics of complex networks.Reviews of modern physics, 74(1):47, 2002

2002
[2]

A note on defective colorings of graphs in surfaces.J

Dan Archdeacon. A note on defective colorings of graphs in surfaces.J. Graph Theory, 11:517–519, 1987

1987
[3]

Differentially private data analysis of social networks via restricted sensitivity

Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. InProceedings of the 4th Conference on Innovations in Theo- retical Computer Science, ITCS ’13, page 87–96, New York, NY, USA, 2013. Association for Computing Machinery

2013
[4]

O. V. Borodin, A. O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k.J. Graph Theory, 65(2):83–93, October 2010. 10

2010
[5]

Private graph colouring with limited defectiveness.arXiv preprint arXiv:2404.18692, 2024

Aleksander BG Christiansen, Eva Rotenberg, Teresa Anna Steiner, and Juliette Vlieghe. Private graph colouring with limited defectiveness.arXiv preprint arXiv:2404.18692, 2024

arXiv 2024
[6]

Li, Quanquan C

Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors,33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 ofLeibniz Int...

2025
[7]

The algorithmic foundations of differential privacy.Foundations and Trends®in Theoretical Computer Science, 9(3–4):211–407, 2014

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy.Foundations and Trends®in Theoretical Computer Science, 9(3–4):211–407, 2014

2014
[8]

North-Holland Publishing Co., NLD, 2004

Martin Charles Golumbic.Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathe- matics, Vol 57). North-Holland Publishing Co., NLD, 2004

2004

Show all 20 references

[9]

Polynomial algorithms for perfect graphs

Martin Gr¨ otschel, Lov´ asz L´ aszl´ o, and Alexander Schrijver. Polynomial algorithms for perfect graphs. Annals of Discrete Math., 21:325–327, 01 1985

1985
[10]

Differentially pri- vate combinatorial optimization

Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially pri- vate combinatorial optimization. InProceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, page 1106–1125, USA, 2010. Society for Industrial and ...

2010
[11]

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. In2009 Ninth IEEE International Conference on Data Mining, pages 169–178, 2009

2009
[12]

Explicit and implicit dynamic coloring of graphs with bounded arboricity.CoRR, abs/2002.10142, 2020

Monika Henzinger, Stefan Neumann, and Andreas Wiese. Explicit and implicit dynamic coloring of graphs with bounded arboricity.CoRR, abs/2002.10142, 2020

2002 arXiv
[13]

Approximate graph coloring by semidefinite pro- gramming, 1998

David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite pro- gramming, 1998

1998
[14]

Karp.Reducibility among Combinatorial Problems, pages 85–103

Richard M. Karp.Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972

1972
[15]

Private analysis of graph structure.ACM Trans

Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure.ACM Trans. Database Syst., 39(3), October 2014

2014
[16]

Analyzing graphs with node differential privacy

Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing graphs with node differential privacy. InProceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, TCC’13, page 457–476, Berlin, Heidelberg, 2013. Springer-Verlag

2013
[17]

Analyzing graphs with node differential privacy

Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing graphs with node differential privacy. InTheory of Cryptography Conference, pages 457–476. Springer, 2013

2013
[18]

Analyzing graphs with node differential privacy

Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing graphs with node differential privacy. InProceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, TCC’13, pages 457–476, Berlin, Heidelberg, 2013. Springer-Verlag

2013
[19]

Snap: A general-purpose network analysis and graph-mining library

Jure Leskovec and Rok Sosiˇ c. Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1–20, 2016

2016
[20]

D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems.The Computer Journal, 10(1):85–86, 01 1967. 11 A Additional Results on Synthetic Graphs Onsynthetic networks, Figure 3 compares the above algorithms ...

1967

Pith tools

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

[1] [1]

Statistical mechanics of complex networks.Reviews of modern physics, 74(1):47, 2002

R´ eka Albert and Albert-L´ aszl´ o Barab´ asi. Statistical mechanics of complex networks.Reviews of modern physics, 74(1):47, 2002

2002

[2] [2]

A note on defective colorings of graphs in surfaces.J

Dan Archdeacon. A note on defective colorings of graphs in surfaces.J. Graph Theory, 11:517–519, 1987

1987

[3] [3]

Differentially private data analysis of social networks via restricted sensitivity

Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. InProceedings of the 4th Conference on Innovations in Theo- retical Computer Science, ITCS ’13, page 87–96, New York, NY, USA, 2013. Association for Computing Machinery

2013

[4] [4]

O. V. Borodin, A. O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k.J. Graph Theory, 65(2):83–93, October 2010. 10

2010

[5] [5]

Private graph colouring with limited defectiveness.arXiv preprint arXiv:2404.18692, 2024

Aleksander BG Christiansen, Eva Rotenberg, Teresa Anna Steiner, and Juliette Vlieghe. Private graph colouring with limited defectiveness.arXiv preprint arXiv:2404.18692, 2024

arXiv 2024

[6] [6]

Li, Quanquan C

Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors,33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 ofLeibniz Int...

2025

[7] [7]

The algorithmic foundations of differential privacy.Foundations and Trends®in Theoretical Computer Science, 9(3–4):211–407, 2014

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy.Foundations and Trends®in Theoretical Computer Science, 9(3–4):211–407, 2014

2014

[8] [8]

North-Holland Publishing Co., NLD, 2004

Martin Charles Golumbic.Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathe- matics, Vol 57). North-Holland Publishing Co., NLD, 2004

2004