Communication-Efficient Publication of Sparse Vectors under Differential Privacy

Quentin Hillebrand; Tetsuo Shibuya; Vorapong Suppakitpaisarn

REVIEW 2 major objections 4 minor 36 references

Communication-Efficient Publication of Sparse Vectors under Differential Privacy

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read The paper proves that randomized response on sparse vectors can be compressed to O(εd) communication and O(d) computation, preserving the exact output distribution under 2αε-metric differential privacy.

desk verdict Nice compression idea, but the privacy proof is broken: m=βεd leaks the sparsity d through the transcript length, so Theorem 5's 2αε-metric DP guarantee is false as stated. read the letter →

arxiv 2506.20234 v1 pith:UXLG62YH submitted 2025-06-25 cs.CR

Quentin Hillebrand , Vorapong Suppakitpaisarn , Tetsuo Shibuya This is my paper · ORCID

classification cs.CR

keywords DifferentialprivacyMetricRandomizedresponseSparsevectorsPoissonprivaterepresentationCommunicationcostLocalGraph

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

This paper tries to establish that publishing a high-dimensional sparse vector under metric differential privacy need not be expensive: a user can send a compressed randomized response whose expected length is O(εd) bits, where ε is the privacy budget and d is the number of non-trivial entries, instead of the Ω(n) bits of a naive randomized response. The claimed compression is exact in distribution: the server's reconstructed vector is identically distributed to the randomized response of the original vector, so downstream estimators designed for randomized response remain valid. If the claim holds, private data collection for social-network adjacency, user-item ratings, and SNP data becomes cheaper than even the non-private sparse representation, and smaller ε—stronger privacy—makes communication cheaper rather than more expensive. The paper supports the claim with a theoretical analysis (Theorems 5–7) and experiments on three application datasets.

What carries the argument

Poisson Private Representation (PPR): a method from [24] that simulates any differentially private mechanism by having the user and server share a counter-based PRNG and a candidate distribution Q; the user transmits only the index K of the draw from Q that is accepted as the mechanism's output, so the server's reconstruction has the same distribution as the original mechanism. The paper's contribution is wrapping PPR in a random partitioning: a public random permutation φ splits the vector into m = βεd chunks, keeping the expected number of non-trivial elements per chunk constant, and the likelihood ratio dP/dQ is evaluated by Algorithm 3, which multiplies $e^{\varepsilon}$ or $e^{-\varepsilon}$ only over the coordinates where the private vector differs from the reference. This machinery turns PPR's per-chunk cost into something that scales with d rather than n, making both communication and computation linear in d.

What would settle it

Run Algorithm 1 on the all-zero vector and on the vector with a single 1 at the same ε, α, β; the first transcript is empty (m = 0) and the second has m = βε chunk indices, so the output supports are disjoint. For the second input, the outcome corresponding to its own transcript has positive probability, while under the first input that outcome has probability 0, giving an unbounded ratio P[M(x) ∈ S] / P[M(x′) ∈ S] for two Hamming-distance-1 inputs and refuting the claimed 2αε-metric differential privacy.

Watch

Extended reading notes

Core claim

The central discovery is that Poisson Private Representation (PPR), which normally has communication cost that grows with the vector's length n, can be made to depend only on the sparsity d if the vector is first randomly permuted and split into m = βεd chunks, each carrying a constant expected number of non-trivial entries. The encoding algorithm, Algorithm 1, applies PPR independently to each chunk with candidate distribution equal to randomized response applied to the reference vector; Algorithm 2 decodes any coordinate in constant time using counter-based PRNGs; and Algorithm 3 computes the required likelihood ratio dP/dQ using only the d′ coordinates where the input differs from the reference, avoiding generation of the full vector. The paper proves that the output is identically distributed to randomized response, that the combined mechanism satisfies 2αε-metric differential privacy by parallel composition (Theorem 5), that expected communication is O(εd) (Theorem 6), and that expected computation is O(d) (Theorem 7), all independent of n.

Load-bearing premise

The argument stands or falls on the assumption that choosing the chunk count m = βεd, which reveals the private sparsity d, does not itself leak anything — so a user with d = 0 and a user with d = 1 may be compared.

Editorial extensions

If this is right

In a social network, each user can publish their adjacency list under edge-local differential privacy with communication proportional to their degree d rather than the number of nodes n, enabling the two-step triangle and cycle counting frameworks to operate at a fraction of the previous communication cost.
Recommendation-system interaction matrices can be published with upload cost proportional to the number of items a user has rated, making local private collection feasible at the scale of millions of items.
For genomic SNP data, a user sends communication proportional to the number of locations where they differ from the most frequent variant, with a reference vector built from population frequencies.
Because the released distribution is exactly randomized response, any estimator, unbiasedness property, or post-processing that works on randomized response works unchanged on the compressed output.
As ε decreases, m = βεd decreases too, so stronger privacy reduces communication cost — the opposite of the behavior of prior communication-constrained randomized response schemes.

Reading between the lines

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

The same random-chunking wrapper could plausibly compress other local mechanisms beyond randomized response: any mechanism whose likelihood ratio against a public reference distribution is nonzero only on a sparse set of coordinates can in principle reuse Algorithm 3's coordinate-local ratio computation.
Because the compressed output is identical in distribution to randomized response, the algorithm can be dropped into existing downstream pipelines—subgraph counting, synthetic graph generation, common-neighbor estimation—without re-deriving their error or unbiasedness guarantees.
The cost reversal (smaller ε lowers communication) suggests a practical operating point: systems could automatically tighten privacy when bandwidth is scarce, a trade-off direction that previous communication-constrained schemes did not offer.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

The core idea here is genuinely new and worth thinking about: randomly partition a sparse vector into m chunks so each chunk has O(1) non-zeros in expectation, then run PPR per chunk and compute the likelihood ratio only on the d coordinates that differ from a public reference. Conditional on a fixed m, the communication and computation analyses are coherent, and the experiments on MovieLens, 1000 Genomes, and the Wikipedia graph are reasonable. The random partitioning trick and the O(d) ratio computation are solid contributions that go beyond the contiguous chunking in [24].

The problem is the privacy accounting. Section 4 sets m = βεd, where d is the private number of non-zero entries. Algorithm 1 outputs a tuple of m PPR messages, so the output length itself is a deterministic function of d. The proof of Theorem 5 applies parallel composition to a fixed set of m chunks and completely ignores that m is data-dependent. The stress-test example is decisive: take v0 = 0ⁿ and v1 = e_i at Hamming distance 1. For v0, m=0 and the output is the empty tuple with probability 1. For v1, m>0 and the output is never empty. Let S={∅}; then Pr[M(v0)∈S]=1 while Pr[M(v1)∈S]=0, violating the metric DP inequality for any finite α, ε. So the 2αε-metric DP guarantee is false as written.

There's also a smaller issue in Theorem 1: the direction of the binomial-vs-hypergeometric inequality is reversed relative to Hoeffding's Theorem 4. The application in Theorem 7 uses the correct direction (hypergeometric is less variable), so this looks like a typo, not a load-bearing error.

The consequence is that the headline claims — communication O(εd) and computation O(d) independent of n — rest on an algorithm that does not actually meet its privacy guarantee. If m were fixed to a public upper bound on d, the privacy proof could be repaired, but then communication would depend on d_max, not d, and the main practical advantage would weaken. The paper does not offer that repair.

I still think this is a serious paper in the sense that the authors are thinking clearly about a real problem and the idea is worth exploring. The flaw is a specific, fixable-in-principle oversight rather than incoherence. But as it stands, the central theorem is false, so I would not cite it as a privacy-preserving mechanism. For a reading group on differential privacy, it's a great example of data-dependent transcript length breaking composition arguments.

Recommendation: send it to peer review — a good referee will catch this and may be able to suggest the fix — but be prepared to reject unless the privacy analysis is reworked.

Referee Report

2 major / 4 minor

Summary. The paper proposes a protocol for releasing randomized-response-obfuscated sparse vectors under metric differential privacy, with communication and computation costs claimed to depend on the sparsity d rather than the vector length n. The protocol (Algorithm 1) randomly permutes the coordinates, partitions them into m chunks, and compresses each chunk's randomized response using the Poisson Private Representation (PPR) of Liu et al. [24]; Algorithm 2 decodes any coordinate, and Algorithm 3 computes the likelihood ratio using only the non-reference coordinates. Section 4 sets m = βεd and claims that the mechanism satisfies 2αε-metric differential privacy (Theorem 5), has O(εd) expected communication (Theorem 6), and O(d) expected computation (Theorem 7). Section 5 describes applications to social-network adjacency lists, recommendation ratings, and SNP data, and Section 6 reports experiments on MovieLens, 1000 Genomes, Wikipedia, and Google+ data.

Significance. If valid, the main result would be an important advance: an exact, distribution-preserving randomized-response publication scheme whose communication scales as O(εd), potentially beating the non-private Ω(d log n) cost for sparse vectors, with experiments suggesting large practical gains. The paper deserves credit for a concrete protocol design, an anonymous reproducible implementation, and a fairly extensive experimental evaluation across several domains. However, the headline privacy theorem is false as stated because the transcript length is data-dependent, so the claimed privacy–communication trade-off is not established. The computational complexity analysis also relies on a misstated version of Hoeffding's inequality. The core idea of random chunking to make PPR tractable may be salvageable in a revised form, but not with the current privacy guarantee.

major comments (2)

[§4, Theorem 5 and Algorithm 1] The privacy proof treats m as a fixed parameter, but §4 sets m = βεd, where d is the private Hamming distance to the reference. The output of Algorithm 1 is a tuple of length m, so the transcript length is an observable deterministic function of d. Let v0 be the all-zero vector and v1 a vector with a single 1; then H(v0, v1) = 1. For v0, m = 0 and the output is the empty tuple with probability 1; for v1, m = βε > 0 and the output is a non-empty tuple, so the two output supports are disjoint. Taking S = {∅} gives P[M(v0) ∈ S] = 1 and P[M(v1) ∈ S] = 0, so the required 2αε-metric DP inequality fails for every finite α and ε. Parallel composition can only be applied to a fixed, data-independent set of chunks, and cannot absorb a data-dependent output length. This invalidates the central privacy claim and, with it, the claimed privacy–communication trade-off.
[§2.1, Theorem 1] The displayed inequality is reversed relative to Hoeffding's Theorem 4. For a continuous convex function f, with Y hypergeometric(N, K, n) and X binomial(n, K/N), the correct Hoeffding bound is E[f(Y)] ≤ E[f(X)], since the hypergeometric is less spread out than the binomial with the same mean. The paper states E[f(X)] ≤ E[f(Y)]. Moreover, the proof of Theorem 7 invokes Theorem 1 to upper-bound E[C_i(d_i)] by the expectation under a binomial Y, which uses the correct direction. The theorem statement should be corrected; as written it is false.

minor comments (4)

[§2.4, Theorem 4] The displayed bound appears to be missing a division sign: it reads "log2 3.56 min{(α−1)/2,1}" where the discussion immediately before it has "log2(3.56/min{(α−1)/2,1})"; the same typo appears in the proof of Theorem 6.
[§1.1] The sentence "our precision is 104 better than any previous works" presumably means 10^4; please use math mode or superscript formatting.
[§6.1] The statement that "all 1,000 executions maintain a manageable execution time" is informal; reporting a maximum and a high percentile would make the variance claim interpretable.
[Algorithm 2] The input is declared as a list of distributions (Q1, ..., Qn), but the pseudocode uses only Q_i for the queried index; clarify whether the list contains per-coordinate or per-chunk candidate distributions.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main mechanism is built by composing an external PPR black box with a novel chunking scheme; the O(εd) bounds follow from that composition rather than being assumed.

full rationale

The claimed derivation chain is not circular. Randomized response is defined in Definition 2 and used as the baseline; Algorithm 1 does not redefine randomized response in terms of its own output. It partitions the vector into m chunks and applies PPR from [24] to each chunk. Theorems 3 and 4 are imported from [24], an external and non-self-cited source, and are not re-derived from the paper's conclusions. The distributional identity with randomized response follows from PPR's exact-simulation property applied independently per coordinate/chunk, so the central 'identical output distribution' claim is supported by an external theorem rather than assumed. The communication bound in Theorem 6 is a direct summation: E[log K_i] <= D(P_i||Q_i)+O(1) from Theorem 4 of [24], D(P_i||Q_i) <= εd_i from Lemma 1, and the chosen m=βεd makes the sum O(εd). The computation bound in Theorem 7 uses the correct Hoeffding stochastic-dominance direction (hypergeometric expectation bounded by binomial expectation) and the same parameterization; the paper's statement of Theorem 1 has the inequality reversed, but the application in Theorem 7 uses the correct direction, so this is a typographical/correctness issue rather than a circular reduction. The self-citations [10] and [11] appear only as application-level conveniences (e.g., encoding lower-index neighbors), not as load-bearing justification for the privacy, communication, or correctness theorems. The genuine vulnerability of the paper—m=βεd depends on the private d, so transcript length leaks sparsity and the parallel-composition argument in Theorem 5 is invalid for differing d—is a privacy correctness flaw, not a case where the paper's conclusion is equivalent to its input by construction. Hence no circular step is present.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claims rest on external PPR theorems, standard probability results, and a public reference model. No new physical or mathematical entities are introduced. The only hand-chosen values are β and α.

free parameters (2)

β (chunk count multiplier) = 2 (default)
The number of chunks is m = βεd. The asymptotic claims hold for any fixed β > 0, but the constants and the range of εd considered depend on it. The default value 2 is chosen after experiments in the appendix.
α (PPR rejection parameter) = 2 (default)
PPR from [24] with parameter α gives a 2αε privacy guarantee. The value α = 2 is chosen by the authors and is not derived from first principles.

assumptions (5)

domain assumption PPR simulation preserves the output distribution and satisfies 2αε-metric DP (Theorem 3 of [24]).
The central correctness and privacy arguments treat PPR as a black box from prior work.
standard math Counter-based PRNGs can generate the i-th sample in constant time (Theorem 2 of [29]).
Needed for the server to decode Gen(Q_i, G(sK_q+r)) in constant time.
standard math Hoeffding's comparison between binomial and hypergeometric expectations (Theorem 4 of [13]).
Used in Theorem 7 to bound the expected computational cost. The paper states the inequality direction incorrectly.
standard math Parallel composition for metric differential privacy.
Used in Theorem 5 to combine per-chunk privacy guarantees, without accounting for the data-dependent number of chunks.
domain assumption The reference vector is public and known to the server and users.
Required by Algorithm 1 to define the candidate distributions Q_i. The authors state this assumption in the proof of Theorem 6.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Communication-Efficient Publication of Sparse Vectors under Differential Privacy." pith.science (2026). https://pith.science/paper/UXLG62YH

@misc{pith2026250620234,
  author       = {Pith},
  title        = {Pith review of: Communication-Efficient Publication of Sparse Vectors under Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UXLG62YH}},
  note         = {Machine review of arXiv:2506.20234}
}

abstract

In this work, we propose a differentially private algorithm for publishing matrices aggregated from sparse vectors. These matrices include social network adjacency matrices, user-item interaction matrices in recommendation systems, and single nucleotide polymorphisms (SNPs) in DNA data. Traditionally, differential privacy in vector collection relies on randomized response, but this approach incurs high communication costs. Specifically, for a matrix with $N$ users, $n$ columns, and $m$ nonzero elements, conventional methods require $\Omega(n \times N)$ communication, making them impractical for large-scale data. Our algorithm significantly reduces this cost to $O(\varepsilon m)$, where $\varepsilon$ is the privacy budget. Notably, this is even lower than the non-private case, which requires $\Omega(m \log n)$ communication. Moreover, as the privacy budget decreases, communication cost further reduces, enabling better privacy with improved efficiency. We theoretically prove that our method yields results identical to those of randomized response, and experimental evaluations confirm its effectiveness in terms of accuracy, communication efficiency, and computational complexity.

Figures

Figures reproduced from arXiv: 2506.20234 by the authors.

**Figure 1.** Communication cost and the execution time in [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

**Figure 4.** The absolute error in estimating the number of [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

Figures from the paper (5 more)

**Figure 2.** Figure 2: Communication cost of our algorithm for 1,000 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png]

**Figure 6.** Figure 6: The average ℓ2 error in the estimation of the number of triangles in the Wiki graph for 3 different algorithms We observe that, for the same level of accuracy, our method reduces communication cost by a factor of more than 100. Furthermore, at the communication cost u…

**Figure 5.** Figure 5: The communication cost and the execution time of [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

**Figure 7.** Figure 7: The communication cost of our algorithm on 1000 [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]

**Figure 8.** Figure 8: The execution time of our algorithm on 1000 users [PITH_FULL_IMAGE:figures/full_fig_p010_8.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 34 canonical work pages

[24]

Yanxiao Liu, Wei-Ning Chen, Ayfer Özgür, and Cheuk Ting Li. 2024. Universal exact compression of differentially private mechanisms. NeurIPS 2024

work page 2024
[1]

Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. 2013. Geo-indistinguishability: differential privacy for location-based systems. In SIGSAC 2013, 901–914

work page 2013
[2]

Arnaud Berlioz, Arik Friedman, Mohamed Ali Kaafar, Roksana Boreli, and Shlomo Berkovsky. 2015. Applying differential privacy to matrix factorization. In RecSys 2015, 107–114

work page 2015
[3]

1000 Genomes Project Consortium et al. 2015. A global reference for human genetic variation. Nature, 526, 7571, 68

work page 2015
[4]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006. Calibrating noise to sensitivity in private data analysis. In TCC 2006, 265–284

work page 2006
[5]

Ulfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Ran- domized aggregatable privacy-preserving ordinal response. In SIGSAC 2014, 1054–1067

work page 2014
[6]

Vitaly Feldman and Kunal Talwar. 2021. Lossless compression of efficient private local randomizers. In ICML 2021, 3208–3219

work page 2021
[7]

Chen Gao, Chao Huang, Dongsheng Lin, Depeng Jin, and Yong Li. 2020. DPLCF: Differentially private local collaborative filtering. In SIGIR 2020, 961–970

work page 2020

Show all 36 references

[8]

Maxwell Harper and Joseph A

F. Maxwell Harper and Joseph A. Konstan. 2015. The MovieLens datasets: History and context. ACM Trans. Interact. Intell. Syst. , 5, 4

2015
[9]

Yizhang He, Kai Wang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2024. Common neighborhood estimation over bipartite graphs under local differential privacy. PACMMOD 2024, 2, 6, 1–26

2024
[10]

Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. 2023. Communication cost reduction for subgraph counting under local differential privacy via hash functions. arXiv preprint arXiv:2312.07055

2023 arXiv
[11]

Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. 2025. Cycle counting under local differential privacy for degeneracy-bounded graphs. STACS 2025

2025
[12]

Yassine Himeur, Shahab Saquib Sohail, Faycal Bensaali, Abbes Amira, and Mamoun Alazab. 2022. Latest trends of security and privacy in recommender systems: a comprehensive review and future perspectives.Computers & Security, 118, 102746

2022
[13]

Wassily Hoeffding. 1963. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association , 58, 301, 13–30

1963
[14]

David A Huffman. 1952. A method for the construction of minimum-redundancy codes. Proceedings of the IRE , 40, 9, 1098–1101

1952
[15]

Mathias Humbert, Erman Ayday, Jean-Pierre Hubaux, and Amalio Telenti. 2014. Reconciling utility with privacy in genomics. In WPES 2014, 11–20

2014
[16]

Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2021. Locally dif- ferentially private analysis of graph statistics. In USENIX Security 2021, 983– 1000

2021
[17]

Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2022. Communication- efficient triangle counting under local differential privacy. In USENIX Security 2022, 537–554

2022
[18]

Lee, Kobbi Nissim, Sofya Raskhod- nikova, and Adam Smith

Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhod- nikova, and Adam Smith. 2011. What can we learn privately? SIAM Journal on Computing, 40, 3, 793–826

2011
[19]

Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Predicting posi- tive and negative links in online social networks. In WWW 2010, 641–650

2010
[20]

Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Signed networks in social media. In CHI 2010, 1361–1370

2010
[21]

Jure Leskovec and Julian Mcauley. 2012. Learning to discover social circles in ego networks. NIPS 2012, 25, 1–9

2012
[22]

Cheuk Ting Li and Abbas El Gamal. 2018. Strong functional representation lemma and applications to coding theorems. IEEE Transactions on Information Theory, 64, 11, 6967–6978

2018
[23]

Shang Liu, Hao Du, Yang Cao, Bo Yan, Jinfei Liu, and Masatoshi Yoshikawa
[25]

Pasin Manurangsi and Warut Suksompong. 2023. Differentially private fair division. AAAI 2023, 5814–5822

2023
[26]

Frank D McSherry. 2009. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In SIGMOD 2009, 19–30

2009
[27]

Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. 2017. Generating synthetic decentralized social graphs with local differential privacy. In CCS 2017, 425–438

2017
[28]

Sheldon M Ross. 1976. A first course in probability . Vol. 2. Macmillan New York

1976
[29]

John K Salmon, Mark A Moraes, Ron O Dror, and David E Shaw. 2011. Parallel random numbers: as easy as 1, 2, 3. In SC 2011, 1–12

2011
[30]

Abhin Shah, Wei-Ning Chen, Johannes Balle, Peter Kairouz, and Lucas Theis
[31]

Yue Wang, Xintao Wu, and Donghui Hu. 2016. Using randomized response for differential privacy preserving data collection. In EDBT/ICDT 2016 number 35

2016
[32]

Akito Yamamoto and Tetsuo Shibuya. 2024. Privacy-Optimized Randomized Response for Sharing Multi-Attribute Data. In ISCC 2024, 1–8

2024
[33]

Emre Yilmaz, Erman Ayday, Tianxi Ji, and Pan Li. 2020. Preserving genomic privacy via selective sharing. In WPES 2020, 163–179

2020
[34]

Emre Yilmaz, Tianxi Ji, Erman Ayday, and Pan Li. 2022. Genomic data sharing under dependent local differential privacy. In CODASPY 2022, 77–88. Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya APPENDIX: ADDITIONAL EXPERIMENTAL RESULTS Results on Movie Lens Data...

2022
[2022]

In AISTATS 2022, 7680–7723

Optimal compression of locally differentially private mechanisms. In AISTATS 2022, 7680–7723

2022
[2025]

ICDE 2025

PGB: Benchmarking differentially private synthetic graph generation algorithms. ICDE 2025

2025

Pith tools

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

[1] [24]

Yanxiao Liu, Wei-Ning Chen, Ayfer Özgür, and Cheuk Ting Li. 2024. Universal exact compression of differentially private mechanisms. NeurIPS 2024

work page 2024

[2] [1]

Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. 2013. Geo-indistinguishability: differential privacy for location-based systems. In SIGSAC 2013, 901–914

work page 2013

[3] [2]

Arnaud Berlioz, Arik Friedman, Mohamed Ali Kaafar, Roksana Boreli, and Shlomo Berkovsky. 2015. Applying differential privacy to matrix factorization. In RecSys 2015, 107–114

work page 2015

[4] [3]

1000 Genomes Project Consortium et al. 2015. A global reference for human genetic variation. Nature, 526, 7571, 68

work page 2015

[5] [4]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006. Calibrating noise to sensitivity in private data analysis. In TCC 2006, 265–284

work page 2006

[6] [5]

Ulfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Ran- domized aggregatable privacy-preserving ordinal response. In SIGSAC 2014, 1054–1067

work page 2014

[7] [6]

Vitaly Feldman and Kunal Talwar. 2021. Lossless compression of efficient private local randomizers. In ICML 2021, 3208–3219

work page 2021

[8] [7]

Chen Gao, Chao Huang, Dongsheng Lin, Depeng Jin, and Yong Li. 2020. DPLCF: Differentially private local collaborative filtering. In SIGIR 2020, 961–970

work page 2020