Pith. sign in

REVIEW 3 major objections 5 minor 40 references

Lightweight Protocols for Distributed Private Quantile Estimation

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

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

Pith's one-line read Adaptive local differential privacy settles the sample complexity of private quantile estimation at $\Theta(\log B/(\varepsilon^2\alpha^2))$ users, each sending one bit.

desk verdict Clean adaptive LDP quantile result with a solid main proof and one completeness gap in the adversarial BayeSS extension; worth refereeing but needs a fuller Appendix E. read the letter →

arxiv 2502.02990 v1 pith:SDBTW4WA submitted 2025-02-05 cs.CR

Anders Aamand , Fabrizio Boninsegna , Abigail Gentle , Jacob Imola , Rasmus Pagh This is my paper · ORCID
classification cs.CR MSC 68P2768W20
keywords localdifferentialprivacyquantileestimationnoisybinarysearchadaptiveprotocolsshufflesamplecomplexityrandomizedresponsemedian
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 claims that a server can estimate any quantile of a distributed dataset with only $O(\log B/(\varepsilon^2 \alpha^2))$ users, each sending one bit, provided the server is allowed to choose queries adaptively and each user answers under local differential privacy with budget $\varepsilon$. The protocol achieves this by converting median estimation into a noisy binary search over the empirical cumulative distribution, then proving that the search routine still succeeds when the coins' biases drift because users are sampled without replacement. A matching lower bound shows no adaptive protocol can use asymptotically fewer users in the high-privacy regime, so the result is optimal. The same machinery yields a shuffle-differential-privacy protocol using $O((1/\alpha^2 + 1/\varepsilon^2)\log B \sqrt{\log(1/\delta)\log\log B/\beta})$ users with $\log_2 B$ rounds. A separate lower bound shows non-adaptive protocols must pay an extra $\log B$ factor, establishing that adaptivity is what buys the improvement.

What carries the argument

The central object is the adversarial noisy binary search problem $\mathrm{AdvMonotonicNBS}$: an ordered list of $B$ coins has unknown monotone head probabilities $p_1 \leq \cdots \leq p_B$, and each time the algorithm queries coin $j$ an adversary may replace the realized bias by any $p$ with $|p-p_j| \leq c\alpha$; the goal is to return a coin whose interval $[p_i, p_{i+1}]$ intersects $[\tau-\alpha(1+c), \tau+\alpha(1+c)]$. The paper proves (Theorem 3.2) that the Bayesian Screening Search algorithm solves this with $O(\log B/\alpha^2)$ coin flips and high probability. The proof machinery is a potential function $\Phi$ over the Bayesian posterior: on a 'bad' query the potential gains at least $(1-12\gamma)C_{\tau,\alpha}$ in expectation, while on a 'good' query it loses at most $11C_{\tau,\alpha}$, and Azuma's inequality then shows the potential crosses zero only with probability $B^{-\lambda}$. The companion Lemma 3.1, proved by a martingale difference argument, bounds the drift of the remaining-users CDF by $\alpha$ over the first $n/2$ steps, which is exactly the adversarial condition the search needs.

What would settle it

Implement $\mathrm{AdvMonotonicNBS}$ with $B=10^6$ coins, $\alpha=0.01$, $c=1$, and $\tau=1/2$, and run the Bayesian Screening Search for $T = C\log B/\alpha^2$ flips with an adversary that sets each realized bias to $p_j + c\alpha$ when $j$ is right of the true $\tau$-coin and to $p_j - c\alpha$ when left; if over 1000 independent runs the fraction of outputs that are $(1/2, 2\alpha)$-good drops well below 0.99, Theorem 3.2 would be refuted. A direct analytical falsifier would be an explicit drift schedule making the expected potential gain on a good query drop below $(1-12\gamma)C_{\tau,\alpha}$, which would break Lemma E.3 and hence the main theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: for every $\alpha \in (0,1/4)$ and $\varepsilon \in (0,1)$, there exists a sequentially adaptive $\varepsilon$-LDP protocol that, with probability at least $1-1/B$, returns an $\alpha$-approximate empirical median of any $n$-user dataset over $[B]$ as long as $n \geq c\log B/(\varepsilon^2\alpha^2)$. Each user is queried once and responds with a single randomized-response bit; the server runs a noisy binary search in which the queried coin is the threshold $[x \leq j]$ after clamping to $\{0,1\}$ and flipping with probability $1/(1+e^\varepsilon)$. The paper's key move is to run this search over users in a random order and to treat the changing empirical CDF as an adversary that may shift each coin's bias by at most $c\alpha$; Theorem 3.2 shows the Bayesian Screening Search still returns a good coin in $O(\log B/\alpha^2)$ flips under such drift. Combined with the lower bound of Theorem 1.2, the sample complexity $\Theta(\log B/(\varepsilon^2\alpha^2))$ is optimal for adaptive protocols, and Theorem 1.3 proves non-adaptive protocols need a strictly larger poly-log factor in $B$.

Load-bearing premise

The load-bearing premise is that the noisy binary search routine still finds a $\tau$-good coin in $O(\log B/\alpha^2)$ queries even when an adversary may shift every coin's bias by up to $c\alpha$ at each query; the paper's proof adapts a previously known potential-function argument and omits the full general proof, so this drift-robustness is the point where the main upper bound would fail if the adaptation is wrong.

Editorial extensions

If this is right

  • Adaptive local differential privacy solves quantile estimation with $\Theta(\log B/(\varepsilon^2\alpha^2))$ users, matching the information-theoretic lower bound up to constants in the high-privacy regime $\varepsilon<1$.
  • Non-adaptive LDP protocols provably need at least $\Omega(\log^2 B/(\alpha^2\varepsilon^2\log^4(1/\alpha)))$ users in the stated regime, so adaptation buys a factor of $\log B$ in sample complexity.
  • The padding reduction shows the median is the hardest quantile: any quantile $q \in (2\alpha, 1-2\alpha)$ inherits the upper and lower bounds up to constants.
  • Shuffle differential privacy can keep most of the benefit: with $r=\log_2 B$ shuffled rounds, $n = O((1/\alpha^2+1/\varepsilon^2)\log B \sqrt{\log(1/\delta)\log\log B/\beta})$ users suffice.
  • Communication stays at one bit per user and $O(\log B)$ server-side update time per round, which is why the protocol is described as lightweight.

Reading between the lines

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

  • If the drift-robustness of Theorem 3.2 holds generally, analogous adaptations could improve adaptive LDP algorithms for other sequential estimation problems where sampling without replacement shifts the target, such as repeated range queries or adaptive CDF approximation.
  • The $\log B$ separation between adaptive and non-adaptive protocols likely reflects a general principle: non-interactive local privacy forces each user's message to be usable for all possible queries, while adaptivity lets the server concentrate privacy budget on relevant thresholds; this intuition may transfer to private selection and learning problems.
  • A systematic sweep of $n$ below the constant $c\log B/(\varepsilon^2\alpha^2)$ threshold would calibrate the universal constant for deployment and reveal whether the success probability degrades gracefully or sharply.
  • The shuffle protocol's analysis requires $n = \Omega(\log(1/\delta)/\varepsilon^2)$ for amplification; if shuffling could amplify with smaller batches, the $1/\alpha^2+1/\varepsilon^2$ trade-off would improve to a $1/(\alpha\varepsilon)$ dependence, which the paper identifies as an open direction.
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 studies distributed quantile estimation under local differential privacy (LDP) and shuffle differential privacy. It proposes a sequentially adaptive LDP protocol based on the BayeSS noisy binary search algorithm of Gretta and Price, and claims that any quantile can be estimated with error alpha using O(log B / (epsilon^2 alpha^2)) users, each sending one bit. It further claims a matching lower bound for adaptive LDP protocols, a lower bound for non-adaptive protocols showing a logarithmic-in-B separation, and a shuffle-DP protocol with r = log_2 B adaptive rounds. The technical core is a martingale argument controlling the drift of the empirical CDF under sampling without replacement (Lemma 3.1), an adversarial-drift generalization of BayeSS (Theorem 3.2), and reductions to existing lower bounds of Duchi et al. and Edmonds et al.

Significance. If the main theorems are correct, the paper resolves the sample complexity of sequentially adaptive LDP quantile estimation up to constant factors and establishes a separation between adaptive and non-adaptive local privacy. The paper has several strengths: the martingale argument in Lemma 4.1 is clean, the upper bounds use external results rather than self-citations, the lower-bound reduction from the empirical to the statistical setting is plausible, and the experimental code is released. However, the adversarial-drift generalization of BayeSS is not proved in a self-contained way, the shuffle-DP guarantee is defined per-round rather than for the joint transcript, and the extension of the Edmonds et al. lower bound to the parameter regime needed here is asserted rather than proved. These issues are load-bearing for the paper's central claims, so the manuscript needs substantial revision before the results can be accepted.

major comments (3)
  1. [Appendix E, Lemma E.3 and Theorem E.2] Theorem 3.2 underpins the proof of Theorem 1.1, but its proof via Theorem E.4 is not self-contained. Lemma E.3's good-query analysis imports Lemmas 9, 10, and 13 of Gretta and Price without stating them, and it uses the unstated estimate alpha(log_2 d_{1,0} - log_2 d_{0,0}) <= (6 log 2) C_{tau,alpha} to conclude that the expected potential drop on good queries is at least -11 C_{tau,alpha}. Theorem E.2, the advertised general adversarial-drift statement, is explicitly not proved: the text says 'the proof is identical (see Lemma 6 and Theorem 1 of (Gretta & Price, 2024)), we omit it.' Because the adversarial-drift analysis is the novel component on which the LDP upper bound depends, the authors should provide a complete proof of Theorem E.4 (or Theorem E.2), including statements of all imported lemmas and a verification that their constants remain valid when each queried coin's bias may drift by up to c alpha.
  2. [Definition 2.4 and Appendix G, proof of Theorem G.6] The shuffle-DP definition in Definition 2.4 only requires each round's shuffled batch to be (epsilon, delta)-DP, not the joint transcript. In the proof of Theorem G.6, each of the r = log_2 B rounds is made (epsilon, delta)-DP via Lemma G.5, and no composition step is given; under standard composition the whole protocol is therefore only (r epsilon, r delta)-DP for a user whose data is used in one round and whose influence propagates through later adaptive mechanism choices. Either the theorem must be stated for the weaker per-round guarantee (which would not match the abstract's 'shuffle DP' claim), or the proof must split the privacy budget across rounds, which will change the stated sample complexity.
  3. [Section 3.2, footnote 5, and Theorem F.4] Theorem 1.3 uses a lower bound of Edmonds et al. (2020, Theorem 23) extended from Omega(log^2 B) to general epsilon and alpha. The paper only says 'it is relatively simple to check that their proof extends' and then restates the extension as Theorem F.4. Since this extension is load-bearing for the non-adaptive lower bound and for the claimed separation result, the derivation should either be included in the appendix or the precise conditions on epsilon, alpha, and B under which the extension holds should be proved.
minor comments (5)
  1. [Section 4, proof of Theorem 1.1] The last sentence of the proof says 'j* + 1 is an alpha-approximate median', but the displayed inequalities q^0_{j*} <= 1/2 + alpha and q^0_{j*+1} >= 1/2 - alpha make j* the alpha-approximate median; the output index should be j*, not j* + 1.
  2. [Lemma 3.1, proof] The proof writes Y_t = |{t < i <= 2n : c_i = 0}|, but there are only n users; this should be t < i <= n. Also, applying Lemma 4.1 to n bits gives a tail bound of 2 exp(-alpha^2 n / 4), not 2 exp(-alpha^2 n / 2); the discrepancy is absorbed by the constant C, but the proof should be corrected.
  3. [Theorem F.2] The condition on epsilon is typeset ambiguously: if it is intended as epsilon <= (1/64) sqrt(log B), the proof's requirement epsilon^2 <= log B / 4096 is satisfied, but if it is intended as epsilon <= 1/(64 sqrt(log B)), the condition is much stronger and does not match the proof. Please clarify the typesetting.
  4. [Throughout] There are several typos that should be corrected, including 'Denote the the private mechanism' in Section 2, 'randomized responze' in Appendix C, 'cocnluding' in the proof of Lemma E.3, and 'succes rate' in Section 5.
  5. [Appendix I.1] The hyperparameter c = 0.6 is selected empirically on the same experimental setup used in the main experiments; Section 5 should state clearly that the reported DpBayeSS success rates use this tuned constant, which is separate from the universal constant c in Theorem 1.1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main results reduce LDP and shuffle-DP median estimation to independent external algorithms and lower bounds; the omitted adversarial-drift proof and an indexing slip are completeness or correctness concerns, not self-referential derivation.

full rationale

No load-bearing step of the derivation reduces to its own inputs. Theorem 1.1 reduces LDPemp-median to AdvMonotonicNBS via Lemma 3.1 and Theorem 3.2. Lemma 3.1 is proved in Section 4 by a self-contained martingale/Azuma argument (Lemma 4.1) that does not presuppose the median guarantee. Theorem 3.2 is an adaptation of the BayeSS algorithm of Gretta and Price; the paper proves the median special case (Theorem E.4) and for the general case says 'the proof is identical (see Lemma 6 and Theorem 1 of (Gretta & Price, 2024)), we omit it', which is an omitted external-verification step rather than a circular one, since the cited source is not by the present authors and the median-case proof is sketched in detail. The lower bounds are supported by the independent frameworks of Duchi et al. (2013) and Edmonds et al. (2020); the reductions between quantile estimation and CDF estimation use padding and boosting arguments, not the claimed lower bounds themselves. The shuffle upper bound rests on the external amplification theorem of Feldman et al. (2021), again not on the present paper's assumptions. The only empirically tuned quantity, the constant c = 0.6, is selected in Appendix I.1 ('we chose to use c = 0.6') and appears only in experiments, not in the universal constant of Theorem 1.1. One non-circular technical slip occurs at the end of the proof of Theorem 1.1: the derived bounds q0_j* <= 1/2 + alpha and q0_{j*+1} >= 1/2 - alpha support output j*, while the text concludes 'Therefore j* + 1 is an alpha-approximate median'; this is an indexing inconsistency that affects the exposition of correctness, not the circularity of the argument. Overall, no fitted input is renamed as a prediction and no uniqueness claim is imported from the authors' own prior work.

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

The theory relies on external results from Gretta and Price, Duchi et al., Edmonds et al., and Feldman et al., but none of these are authored by the present authors, so the reliance is not circular. One experimental hyper-parameter is tuned on synthetic data. No new entities are introduced.

free parameters (1)
  • hyperparameter c = 0.6
    Sets alpha_update = c * sqrt(log B / n) in DpBayeSS; chosen empirically on synthetic Pareto data in Figure 2. It affects the experimental evaluation, not the theoretical theorems.
assumptions (5)
  • domain assumption Correctness of the Bayesian Screening Search (BayeSS) algorithm of Gretta and Price, including Lemmas 6, 7, 9, 10, 13
    The adversarial noisy binary search analysis in Appendix E builds directly on these results; the paper adapts Lemma 7 but relies on the original proof structure and several lemmas without reproducing them.
  • standard math Duchi, Jordan and Wainwright (2013) LDP mutual information bound
    Used in the statistical lower bound (Theorem F.1) to upper bound the mutual information between the private outputs and the index of the hard distribution.
  • standard math Edmonds, Nikolov and Ullman (2020) lower bound for privately learning a CDF (Theorem 23)
    Used in the nonadaptive lower bound (Theorem 1.3) after a reduction from median estimation to CDF learning; the paper states the proof extends to general epsilon and alpha with mild assumptions without fully checking the parameter regime.
  • standard math Feldman, McMillan and Talwar (2021) privacy amplification by shuffling
    Used to prove the shuffle protocol (Theorem 1.4), specifically Lemma G.5.
  • standard math Azuma's inequality, Bernstein's inequality, Fano's inequality
    Standard concentration and information-theoretic tools invoked in Lemmas 4.1, G.1, G.2 and F.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lightweight Protocols for Distributed Private Quantile Estimation." pith.science (2026). https://pith.science/paper/SDBTW4WA

@misc{pith2026250202990,
  author       = {Pith},
  title        = {Pith review of: Lightweight Protocols for Distributed Private Quantile Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SDBTW4WA}},
  note         = {Machine review of arXiv:2502.02990}
}
abstract

Distributed data analysis is a large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. We consider two \emph{adaptive} algorithms for estimating one quantile (e.g.~the median) when each user holds a single data point lying in a domain $[B]$ that can be queried once through a private mechanism; one under local differential privacy (LDP) and another for shuffle differential privacy (shuffle-DP). In the adaptive setting we present an $\varepsilon$-LDP algorithm which can estimate any quantile within error $\alpha$ only requiring $O(\frac{\log B}{\varepsilon^2\alpha^2})$ users, and an $(\varepsilon,\delta)$-shuffle DP algorithm requiring only $\widetilde{O}((\frac{1}{\varepsilon^2}+\frac{1}{\alpha^2})\log B)$ users. Prior (nonadaptive) algorithms require more users by several logarithmic factors in $B$. We further provide a matching lower bound for adaptive protocols, showing that our LDP algorithm is optimal in the low-$\varepsilon$ regime. Additionally, we establish lower bounds against non-adaptive protocols which paired with our understanding of the adaptive case, proves a fundamental separation between these models.

Figures

Figures reproduced from arXiv: 2502.02990 by the authors.

Figure 1
Figure 1. Plots 1a compare the three algorithms on the Pareto-like dataset: the left plot shows the success rate for αtest = 0.04 across ε ∈ [0.1, 5], and the right plot shows the c.d.f. of the absolute error for ε = 0.57. Plots 1b compare DpBayeSS and DpNaiveNBS on a uniform dataset with ε = 1: the left plot shows the success rate for different coin domains B for αtest = 0.04, and the right plot shows the c.d.f. of the absol… view at source ↗
Figure 2
Figure 2. Experiments to estimate the best constant c to compute αupdate = c qlog B n . I.1. Hyper-parameter selection To determine the optimal parameter for updating DpBayesLearn given a fixed number of users n, coins B, and varying privacy budgets ε ∈ {0.5, 1, 1.5}, we conducted experiments using DpBayeSS with different update parameters αupdate = c q log B n . These experiments were performed on two distinct datasets gener… view at source ↗
Figure 3
Figure 3. Experiments run over a dataset obtained by sampling n random integers over a random subset of [B]. I.2. Comparison analysis In [PITH_FULL_IMAGE:figures/full_fig_p028_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Experiments for n = 107 and B = 48 , with δ = 10−8 for shuffle DP I.3. Noisy Binary Search with Shuffling When the number of users n is sufficiently large, noisy binary search with shuffling, as described in Section G, can be implemented. The implementation mirrors tha…
Figure 5
Figure 5. Figure 5: Comparison analysis. 30 [PITH_FULL_IMAGE:figures/full_fig_p030_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 20 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]

    Bounded space differentially private quantiles

    Alabi, D., Ben - Eliezer, O., and Chaturvedi, A. Bounded space differentially private quantiles. Trans. Mach. Learn. Res., 2023, 2023. URL https://openreview.net/forum?id=sixOD8YVvM

    work page 2023

  3. [3]

    Aliakbarpour, M., Silver, R., Steinke, T., and Ullman, J. R. Differentially private medians and interior points for non-pathological data. In Guruswami, V. (ed.), 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA , volume 287 of LIPIcs, pp.\ 3:1--3:21, 2024. URL https://doi.org/10.423...

    work page doi:10.4230/lipics.itcs.2024.3 2024

  4. [4]

    Private PAC learning implies finite littlestone dimension

    Alon, N., Livni, R., Malliaris, M., and Moran, S. Private PAC learning implies finite littlestone dimension. In Charikar, M. and Cohen, E. (eds.), Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 , pp.\ 852--860. ACM , 2019. doi:10.1145/3313276.3316312. URL https://doi.org/10.1145/33...

    arXiv 2019

  5. [5]

    Arnold, B. C. Pareto distribution. Wiley StatsRef: Statistics Reference Online, pp.\ 1--10, 2014

    work page 2014

  6. [6]

    and Duchi, J

    Asi, H. and Duchi, J. C. Near instance-optimality in differential privacy. CoRR, abs/2005.10630, 2020. URL https://arxiv.org/abs/2005.10630

    arXiv 2005

  7. [7]

    and Smith, A

    Bassily, R. and Smith, A. Local, private, efficient protocols for succinct histograms. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp.\ 127--135, 2015

    work page 2015

  8. [8]

    Private learning and sanitization: Pure vs

    Beimel, A., Nissim, K., and Stemmer, U. Private learning and sanitization: Pure vs. approximate differential privacy. Theory Comput., 12 0 (1): 0 1--61, 2016. doi:10.4086/TOC.2016.V012A001. URL https://doi.org/10.4086/toc.2016.v012a001

    work page doi:10.4086/toc.2016.v012a001 2016

Show all 40 references
  1. [9]

    Prochlo: Strong privacy for analytics in the crowd

    Bittau, A., Erlingsson, \' U ., Maniatis, P., Mironov, I., Raghunathan, A., Lie, D., Rudominer, M., Kode, U., Tinn \' e s, J., and Seefeld, B. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, Ch...

    2017

  2. [10]

    Differentially private release and learning of threshold functions

    Bun, M., Nissim, K., Stemmer, U., and Vadhan, S. Differentially private release and learning of threshold functions. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pp.\ 634–649, USA, 2015. IEEE Computer Society. ISBN ...

    2015 doi

  3. [11]

    Heavy hitters and the structure of local privacy

    Bun, M., Nelson, J., and Stemmer, U. Heavy hitters and the structure of local privacy. ACM Transactions on Algorithms (TALG), 15 0 (4): 0 1--40, 2019

    2019

  4. [12]

    Differential privacy in the shuffle model: A survey of separations

    Cheu, A. Differential privacy in the shuffle model: A survey of separations. arXiv preprint arXiv:2107.11839, 2021

    2021 arXiv

  5. [13]

    D., Ullman, J

    Cheu, A., Smith, A. D., Ullman, J. R., Zeber, D., and Zhilyaev, M. Distributed differential privacy via mixnets. CoRR, abs/1808.01394, 2018. URL http://arxiv.org/abs/1808.01394

    2018 arXiv

  6. [14]

    D., Ullman, J

    Cheu, A., Smith, A. D., Ullman, J. R., Zeber, D., and Zhilyaev, M. Distributed differential privacy via shuffling. In Ishai, Y. and Rijmen, V. (eds.), Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic...

    2019 doi

  7. [15]

    Privacy at scale: Local differential privacy in practice

    Cormode, G., Jha, S., Kulkarni, T., Li, N., Srivastava, D., and Wang, T. Privacy at scale: Local differential privacy in practice. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD '18, pp.\ 1655–1658, New York, NY, USA, 2018. Association for Co...

    2018

  8. [16]

    Answering range queries under local differential privacy

    Cormode, G., Kulkarni, T., and Srivastava, D. Answering range queries under local differential privacy. Proc. VLDB Endow. , 12 0 (10): 0 1126--1138, 2019. doi:10.14778/3339490.3339496. URL http://www.vldb.org/pvldb/vol12/p1126-cormode.pdf

    2019

  9. [17]

    Frequency estimation under local differential privacy

    Cormode, G., Maddock, S., and Maple, C. Frequency estimation under local differential privacy. Proc. VLDB Endow. , 14 0 (11): 0 2046--2058, 2021. doi:10.14778/3476249.3476261. URL http://www.vldb.org/pvldb/vol14/p2046-cormode.pdf

    2021

  10. [18]

    Learning with privacy at scale., 2017

    Differential Privacy Team, A. Learning with privacy at scale., 2017

    2017

  11. [19]

    Nonparametric differentially private confidence intervals for the median

    Drechsler, J., Globus-Harris, I., Mcmillan, A., Sarathy, J., and Smith, A. Nonparametric differentially private confidence intervals for the median. Journal of Survey Statistics and Methodology, 10 0 (3): 0 804--829, 2022

    2022

  12. [20]

    C., Jordan, M

    Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Local privacy and statistical minimax rates. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA , pp.\ 429--438. IEEE Computer Society, 2013. doi:10.1109/FOCS.20...

    2013 doi

  13. [21]

    C., Jordan, M

    Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113 0 (521): 0 182--201, 2018

    2018

  14. [22]

    and Lei, J

    Dwork, C. and Lei, J. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp.\ 371--380, 2009

    2009

  15. [23]

    Calibrating noise to sensitivity in private data analysis

    Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp.\ 265--284. Springer, 2006

    2006

  16. [24]

    The algorithmic foundations of differential privacy

    Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 9 0 (3--4): 0 211--407, 2014

    2014

  17. [25]

    Edmonds, A., Nikolov, A., and Ullman, J. R. The power of factorization mechanisms in local and central differential privacy. In Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., and Chuzhoy, J. (eds.), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Co...

    2020

  18. [26]

    RAPPOR: randomized aggregatable privacy-preserving ordinal response

    Erlingsson, \' U ., Pihur, V., and Korolova, A. RAPPOR: randomized aggregatable privacy-preserving ordinal response. In Ahn, G., Yung, M., and Li, N. (eds.), Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3-...

    2014

  19. [27]

    Amplification by shuffling: From local to central differential privacy via anonymity

    Erlingsson, \' U ., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., and Thakurta, A. Amplification by shuffling: From local to central differential privacy via anonymity. In Chan, T. M. (ed.), Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms...

    2019 doi

  20. [28]

    Hoeffding’s inequality for supermartingales

    Fan, X., Grama, I., and Liu, Q. Hoeffding’s inequality for supermartingales. Stochastic Processes and their Applications, 122 0 (10): 0 3545--3559, 2012. ISSN 0304-4149. doi:https://doi.org/10.1016/j.spa.2012.06.009. URL https://www.sciencedirect.com/science/article/pii/S03044...

    2012 doi

  21. [29]

    Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling

    Feldman, V., McMillan, A., and Talwar, K. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pp.\ 954--964. IEE...

    2021

  22. [30]

    Differentially private quantiles

    Gillenwater, J., Joseph, M., and Kulesza, A. Differentially private quantiles. In International Conference on Machine Learning, pp.\ 3713--3722. PMLR, 2021

    2021

  23. [31]

    and Price, E

    Gretta, L. and Price, E. Sharp noisy binary search with monotonic probabilities. In Bringmann, K., Grohe, M., Puppis, G., and Svensson, O. (eds.), 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia , volume 297 ...

    2024 doi

  24. [32]

    B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A

    Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K. A., Charles, Z., Cormode, G., Cummings, R., D'Oliveira, R. G. L., Eichner, H., Rouayheb, S. E., Evans, D., Gardner, J., Garrett, Z., Gasc \' o n, A., Ghazi, B., Gibbons, P. B., Grutese...

    2021

  25. [33]

    Privately learning thresholds: Closing the exponential gap

    Kaplan, H., Ligett, K., Mansour, Y., Naor, M., and Stemmer, U. Privately learning thresholds: Closing the exponential gap. In Abernethy, J. D. and Agarwal, S. (eds.), Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria] , volume 125 of Procee...

    2020

  26. [34]

    Karp, R. M. and Kleinberg, R. Noisy binary search and its applications. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp.\ 881--890. Citeseer, 2007

    2007

  27. [35]

    Smooth sensitivity and sampling in private data analysis

    Nissim, K., Raskhodnikova, S., and Smith, A. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp.\ 75--84, 2007

    2007

  28. [36]

    Optimal private median estimation under minimal distributional assumptions

    Tzamos, C., Vlatakis-Gkaragkounis, E.-V., and Zadik, I. Optimal private median estimation under minimal distributional assumptions. Advances in Neural Information Processing Systems, 33: 0 3301--3311, 2020

    2020

  29. [37]

    Wainwright, M. J. Basic tail and concentration bounds, pp.\ 21–57. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019

    2019

  30. [38]

    Locally differentially private protocols for frequency estimation

    Wang, T., Blocki, J., Li, N., and Jha, S. Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security 17), pp.\ 729--745, 2017

    2017

  31. [39]

    Warner, S. L. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60 0 (309): 0 63--69, 1965

    1965

  32. [40]

    J., Zhang, C

    Wilson, R. J., Zhang, C. Y., Lam, W., Desfontaines, D., Simmons - Marengo, D., and Gipson, B. Differentially private SQL with bounded user contribution. Proc. Priv. Enhancing Technol., 2020 0 (2): 0 230--250, 2020. doi:10.2478/POPETS-2020-0025. URL https://doi.org/10.2478/pope...

    2020 doi

Pith tools

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