Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries

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

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

Pith's one-line read The paper claims to break the quadratic barrier on adaptive queries for cardinality sketches, shifting the bound from total queries to per-key participation.

desk verdict The formal per-key participation result is real and worth refereeing, but the abstract's 'exponential queries' claim outruns Theorem 4.1; the headline needs correction before acceptance. read the letter →

arxiv 2502.05723 v1 pith:7FG63APZ submitted 2025-02-08 cs.DS

Edith Cohen , Mihir Singhal , Uri Stemmer This is my paper · ORCID
classification cs.DS MSC 68W2068W2568P05
keywords adaptivequeriescardinalitysketchesbottom-kMinHashdifferentialprivacydataanalysisper-keyparticipationquadraticbarrierrobustestimation
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 claims to break the quadratic barrier on adaptive queries for cardinality sketches. Previous work showed that a sketch of size k fails after roughly $k^{2}$ adaptively chosen queries, no matter the estimator; this paper instead ties the guarantee to per-key participation, showing that a bottom-k MinHash sketch of size k = O($α^{{-2}}$√r $log^{{3/2}}$(n/β)) answers every query within a (1±α) factor with probability 1-β, provided each key appears in at most r query sketches. Since r can be far smaller than the total number of queries, this allows exponentially many queries when the workload spreads across keys. The paper also gives a tracking estimator that deactivates overused keys and degrades gracefully, and reports 12× to 100× gains in simulated workloads.

What carries the argument

The load-bearing object is the fine-grained SQ (statistical query) framework, which reduces robust sketching to adaptive data analysis. Concretely: the random priority vector ρ is the dataset from a product distribution; the query predicate is h_{V,τ}(i, ρ_i) = 1[i ∈ V ∧ ρ_i < τ], so the count over the dataset equals τ|V| in expectation; and the response algorithm is AboveThreshold with per-key 'charging' counters that deactivate a key after r positive queries (Algorithm 1). The analysis chains the privacy of that charging mechanism (Theorem 2.1) to the generalization property of differential privacy (Theorem 2.2), yielding error bounds in which the additive term is O($α^{{-1}}$√r $log^{{3/2}}$(mn/β)) plus α times the query's expectation (Corollary 3.3). Because this error depends on r rather than on total queries t, a bottom-k sketch of size k can be set proportional to √r and still answer an exponential number of adaptive queries.

What would settle it

Run RobustEst (or TRobustEst) with priorities generated by a 2-independent hash family instead of independent U[0,1] draws, and let an adaptive adversary issue queries that concentrate on a single key while keeping per-key participation at r ≈ 0.$002k^{2}$; if the estimator loses (1±α) accuracy at k = C $α^{{-2}}$√r $log^{{3/2}}$(n/β), the independence assumption is load-bearing. Alternatively, try to construct an adaptive sequence with each key in at most r queries that still drives the estimate off by more than α; the theorem predicts none exists.

Watch

Extended reading notes

Core claim

The central discovery is that robustness to adaptive queries can be guaranteed per key rather than per query. The authors reformulate the privacy-based robustness wrapper as an adaptive data analysis problem: the sketch's random priorities ρ = (ρ_1,...,ρ_n) are treated as a dataset drawn from a product distribution, and each query to the sketch becomes a linear threshold query h_{V,τ}(i, ρ_i) = 1[i ∈ V and ρ_i < τ]. Using the Sparse Vector Technique with individual per-key charging, they prove a fine-grained generalization bound in which the number of positive queries per key, r, controls the error. Instantiating this on the bottom-k MinHash sketch with the estimator RobustEst yields Theorem 4.1: for r ≫ log(n/β), sketch size k = O($α^{{-2}}$√r $log^{{3/2}}$(n/β)) answers all queries (1±α)-accurately with probability 1-β, provided each key participates in at most r queries. A second estimator, TRobustEst, tracks each key's participation, deactivates keys that exceed r, and retains accuracy as long as no query's sketch contains more than k/2 deactivated keys and the queries in question have at most αk/4 deactivated keys.

Load-bearing premise

The guarantees require the sketch priorities to be fully independent random draws from a product distribution, not merely k-wise independent or pseudorandom hashes; the privacy-generalization argument that controls adaptive queries collapses without that independence.

Editorial extensions

If this is right

  • Sketch size can be traded against robustness per key: k = O(α^{-2}√r log^{3/2}(n/β)), so reducing the allowed per-key participation r directly reduces the required sketch size.
  • An exponential number of total adaptive queries becomes safe whenever the query distribution spreads over keys so that each key appears in few query sets.
  • The tracking estimator allows a few heavy-hitter keys to exceed the per-key budget: those keys are deactivated, and estimates remain (1±α)-accurate as long as each query sketch has at most αk/4 deactivated keys and none has more than k/2.
  • The same fine-grained ADA reduction is a candidate template for other randomized composable sketches, including k-partition (PCSA) and capping statistics, as the authors conjecture.

Reading between the lines

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

  • A practical deployment reading: workloads with per-user or per-key query limits can safely use far smaller sketches than the total-query bound would suggest; the guarantee degrades only when an adversary concentrates queries on the same keys.
  • If full i.i.d. randomness is truly required, implementations must avoid low-independence hash families; an engineering check is to compare failure rates of 2-independent hashing against a cryptographic hash on an adaptive adversary that targets one key at a time.
  • The per-key charging mechanism is essentially per-key privacy accounting; it could be imported into other interactive data structures, possibly replacing DP with other ADA algorithms where DP's constants are undesirable.
  • For heavy-tailed (Pareto) workloads, the tracking estimator is necessary; the experiments suggest 12×–40× gains, and the gap between uniform (100×) and skewed (12×) distributions indicates where per-key bounds bind.
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.

Referee Report

3 major / 5 minor

Summary. The paper addresses adaptive adversarial queries to composable cardinality sketches, where prior work established a 'quadratic barrier': roughly t = O~(k^2) adaptive queries can be answered by a sketch of size k, and universal O~(k^2)-query attacks exist. The authors propose shifting the barrier to a per-key parameter r: if every key participates in at most r of the query sketches, then a bottom-k MinHash sketch of size k = O(alpha^{-2} sqrt(r) log^{3/2}(n/beta)) answers every query with (1 +/- alpha)-accuracy with probability 1 - beta. To obtain this, they reformulate the robustness wrapper of Hassidim et al. in terms of adaptive data analysis (ADA) with fine-grained per-key generalization guarantees (Section 3), using per-unit privacy charging (Cohen-Lyu) and a DP generalization bound (Dwork et al.; Bassily et al.). Two estimators are analyzed: a stateless basic estimator (Section 4, Theorem 4.1) and a tracking estimator that deactivates overexposed keys (Section 5, Theorem 5.1) with smooth degradation in the fraction of deactivated keys. Experiments on synthetic Uniform and Pareto query workloads report 12x-100x gains over the per-query baseline.

Significance. The per-key-participation formulation is a genuinely useful conceptual step: in realistic workloads where a few heavy-hitter keys dominate, the total query count t can vastly exceed k^2 while r stays moderate, and the paper provides the first composable-sketches result with this kind of data-dependent guarantee. The fine-grained ADA framework (Lemma 3.1, Corollary 3.3) is clean and reusable, and the reduction from robust estimation to linear threshold queries over a product-distributed priority vector is elegant; the proofs are unusually explicit (Lemma 4.2, Propositions 4.4-4.5, Appendices B and C), with each step checkable. The experimental protocol is simple and reproducible. However, the advertised headline claim of handling an exponential number of adaptive queries does not follow from Theorem 4.1 (see major comment 1), and the proof chain contains two repairable gaps (major comments 2 and 3). The per-key barrier-shift idea survives these corrections in a weaker, subexponential form and warrants publication after substantial revision.

major comments (3)
  1. [Abstract and Section 1.3] The claim that the construction can handle an exponential number of adaptive queries provided each key participates in at most r = O~(k^2) queries is not a consequence of Theorem 4.1; in the advertised parameter regime it is actually inconsistent with the theorem. Substituting r = c k^2 alpha^4 into k = O(alpha^{-2} sqrt(r) log^{3/2}(n/beta)) forces log(n/beta) to be bounded by a constant, so n = O(1) and the total number of queries satisfies t <= n r = O(k^2): the quadratic barrier for total queries is not surpassed at all in this regime. If instead one aims for t exponential in k, which requires log n = Omega(k), the theorem forces r = O(alpha^4 k^2 / log^3(n/beta)) = O(alpha^4 / k), contradicting the theorem's own requirement r >> log(n/beta) = Omega(k). Maximizing t <= n r subject to both constraints yields log(n/beta) = O(alpha sqrt(k)) and t = exp(O(alpha sqrt(k))) * poly(k), i.e., subexponential in k. The formal per-key contribution survives in this weaker form, but the abstract and Section 1.3 overstate it; they should be corrected to state the subexponential tradeoff actually proved, or Theorem 4.1 should be strengthened to support the stated claim.
  2. [Section 3, proof of Lemma 3.1] The proof of Lemma 3.1 drops the approximate-DP term from Theorem 2.2. With the stated choices delta = beta/n^2 and T = 2m/beta, the additive term 2Tn*delta equals 4m/n, which is not bounded by the claimed O(log(m/beta)/alpha) under the lemma's hypotheses; in the application of Section 4.3, m is taken to be poly(n), making 4m/n = poly(n), far beyond the O(alpha^{-1} sqrt(r) log^{3/2}(n/beta)) budget that the choice of k must absorb. The gap is locally repairable: choose delta = beta/(2mn), giving 2Tn*delta = 2, and note that log(1/delta) = O(log(n/beta)) because m = poly(n) in the application, so the privacy parameter epsilon = sqrt(r log(1/delta)) * epsilon_0 remains within the required bound after readjusting constants. As written, the chain Lemma 3.1 -> Corollary 3.3 -> Theorem 4.1 is incomplete, and the proof of Theorem 4.1 does not go through without this fix.
  3. [Section 4.3, simulation argument] The sentence 'Observe that for any query sketch S, there is at most one positive test in Algorithm 3. Therefore, per assumption (1) on the input, each index appears in at most r positive tests' does not follow from condition (1) as stated. Condition (1) bounds the number of sketches containing key i, but in the simulation by Algorithm 1 the charges are incurred by all keys i in V_j with rho_i < tau (the full-set predicate h_{V,tau}), and a key can satisfy this without belonging to the sketch whenever the termination threshold tau exceeds the k-th smallest priority of V_j. The missing argument is that, with probability 1 - O(beta), the final tau of each query lies below that k-th order statistic; this follows from T = (1 - alpha)k, the alpha*k/8 noise bound, and the grid spacing, just as the analogous claim is proved for the tracking estimator in Claim C.2 of Appendix C. Once that holds, all charged keys are sketch keys and each key is charged at most r times. Without such an argument, the claim holds only under the stronger set-participation condition that the paper notes as sufficient; the theorem, whose assumption (1) is stated in terms of sketch participation, needs either the missing proof or a restated assumption.
minor comments (5)
  1. [Section 4.1, footnote 4] The formal analysis requires fully independent priorities, i.e., a product distribution over the priority vector rho, because the ADA generalization argument (Lemma 3.1 via Theorem 2.2) is stated for product distributions; the footnote's acknowledgment that implementations use pseudo-random hash maps means the robustness guarantee of Theorem 4.1 is not established for the practical hash families used in implementations, and the abstract's practical framing outruns the theorem. The parenthetical claim that O(log k) bits of representation are sufficient is also unclear (a bottom-k sketch stores k priorities, and the seed for the priority map appears to need Omega(log n) bits) and should be clarified or removed.
  2. [Algorithms 3 and 4] The displayed formula for epsilon_0 is typeset incorrectly in both algorithms: 'epsilon_0 <- alpha/8 4 sqrt(r log(n/(beta/4)))' should presumably read epsilon_0 = (alpha/8)/(4 sqrt(r log(n/(beta/4)))), matching the invocation of Lemma 3.1 with parameters (alpha/8, beta/4).
  3. [Section 3, Lemma 3.1] The hypothesis states r >> log(n/beta), but the proof uses r >> log(1/delta); with the corrected delta = beta/(2mn) from major comment 2, the clean hypothesis becomes r >> log(mn/beta). Since m = poly(n) in the application, these differ only by constants, but the statement and the proof should be made consistent.
  4. [Section 6] The reported 12x-100x gains are point estimates on synthetic data with no variance information; since the stopping rules (10% deactivated threshold, 50% stop) are stochastic, reporting standard errors over a small number of seeds would strengthen the empirical claim.
  5. [Section 4.1] Small typo: 'This standard estimator is know to optimally use' should read 'is known to'. Also, the term 'stateless estimator' in Section 1.3 is slightly misleading because the estimator runs a per-query while loop; the intended meaning is that no state persists across queries, and this could be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central guarantee is derived from a genuine reduction to fine-grained adaptive data analysis, not from fitting or self-referential definitions.

full rationale

The derivation chain is self-contained in the relevant sense. The paper samples priority vectors rho as a dataset, represents each robust-estimator threshold test as a linear query h_{V,tau}=1_{i in V, rho_i<tau}, simulates Algorithm 3 by the privatized charging mechanism of Algorithm 1, and then obtains Theorem 4.1 from Corollary 3.3 by choosing k so that the additive error Delta is below alpha k/8. The per-key parameter r enters only as the privacy charging budget supplied by the input condition (1); it is not fitted after the fact to force the stated sketch size. The experimental constant 0.002 is a simulation parameter, not an input to the proof. The only load-bearing self-citation is Theorem 2.1, attributed to Cohen and Lyu (2023a), which is a prior peer-reviewed privacy theorem used as a black box; it is not re-derived from, nor equivalent to, the paper's own cardinality-estimation claim, so it does not make the argument circular. The abstract's wording 'exponential number of adaptive queries' is stronger than the parameter regime of Theorem 4.1 supports (a correctness concern), but unsupported strength is not circularity. Likewise, footnote 4's full-independence assumption is a stated limitation rather than a hidden reuse of the conclusion. No step in the paper reduces, by construction or by self-citation, to its own inputs.

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

The central claim rests on one imported privacy theorem (Cohen & Lyu 2023a, with author overlap) and on the standard full-randomness model for sketching maps. No new physical or algorithmic entity is postulated; the 'deactivated keys' in the tracking estimator are a server-side state, not an invented entity.

free parameters (1)
  • simulation constant for per-key budget = 0.002
    Section 6 sets r = 0.002 k^2 and the baseline t = 0.002 k^2. This is a hand-picked constant for the empirical demonstration; it does not appear in the theorems, but it determines the reported gain factors.
assumptions (3)
  • standard math Theorem 2.1 (Cohen & Lyu 2023a): privacy of Algorithm 1 with per-unit charging.
    Used as a black box throughout the fine-grained ADA analysis (Lemma 3.1) and both estimator proofs; not reproved here. The result is from prior work by one of the present authors.
  • domain assumption The priorities ρ_i are fully i.i.d. U[0,1] (footnote 4).
    The analysis maps the sketch randomness to a sample from a product distribution; without full independence the DP generalization theorem does not apply to the exact query predicates.
  • standard math The generalization property of DP (Theorem 2.2) holds for product distributions and adaptively chosen predicates.
    The paper supplies a proof in Appendix B, building on Kontorovich et al. (2022); it is a known result rather than an ad hoc assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries." pith.science (2026). https://pith.science/paper/7FG63APZ

@misc{pith2026250205723,
  author       = {Pith},
  title        = {Pith review of: Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7FG63APZ}},
  note         = {Machine review of arXiv:2502.05723}
}
abstract

Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimizing storage, communication, and computational costs. However, recent research has shown that these sketches can fail under {\em adaptively chosen queries}, breaking down after approximately $\tilde{O}(k^2)$ queries, where $k$ is the sketch size. In this work, we overcome this \emph{quadratic barrier} by designing robust estimators with fine-grained guarantees. Specifically, our constructions can handle an {\em exponential number of adaptive queries}, provided that each element participates in at most $\tilde{O}(k^2)$ queries. This effectively shifts the quadratic barrier from the total number of queries to the number of queries {\em sharing the same element}, which can be significantly smaller. Beyond cardinality sketches, our approach expands the toolkit for robust algorithm design.

Figures

Figures reproduced from arXiv: 2502.05723 by the authors.

Figure 1
Figure 1. Number of guaranteed queries for sketch size [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Adversarial Robustness of Sketching and Streaming Algorithms

    cs.DS 2026-07 conditional novelty 2.0 of 10

    A survey monograph unifying the field of adversarially robust streaming: near-optimal robustness for insertion-only streams, poly(n)-space impossibility for turnstile linear sketches, and crypto-based white-box algorithms.

Reference graph

Works this paper leans on

64 extracted references · 55 canonical work pages · cited by 1 Pith paper

  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]

    Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs

    Ahmadian, S. and Cohen, E. Unmasking vulnerabilities: Cardinality sketches under adaptive inputs. In ICML, 2024. URL https://doi.org/10.48550/arXiv.2405.17780

    work page Pith review arXiv doi:10.48550/arxiv.2405.17780 2024

  3. [3]

    J., Guha, S., and McGregor, A

    Ahn, K. J., Guha, S., and McGregor, A. Analyzing graph structure via linear measurements. In Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\ 459--467, 2012. doi:10.1137/1.9781611973099.40. URL https://epubs.siam.org/doi/abs/10.1137/1.9781611973099.40

    doi:10.1137/1.9781611973099.40 2012

  4. [4]

    The space complexity of approximating the frequency moments

    Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58: 0 137--147, 1999

    work page 1999

  5. [5]

    DataSketches , Accessed: 2024

    Apache Software Foundation . DataSketches , Accessed: 2024. URL https://datasketches.apache.org. Apache Software Foundation Documentation

    work page 2024

  6. [6]

    Synthesizing robust adversarial examples

    Athalye, A., Engstrom, L., Ilyas, A., and Kwok, K. Synthesizing robust adversarial examples. In International conference on machine learning, pp.\ 284--293. PMLR, 2018

    work page 2018

  7. [7]

    A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

    Attias, I., Cohen, E., Shechner, M., and Stemmer, U. A framework for adversarial streaming via differential privacy and difference estimators. CoRR, abs/2107.14527, 2021

    work page Pith review arXiv 2021

  8. [8]

    S., Kumar, R., Sivakumar, D., and Trevisan, L

    Bar-Yossef, Z., Jayram, T. S., Kumar, R., Sivakumar, D., and Trevisan, L. Counting distinct elements in a data stream. In RANDOM. ACM, 2002

    work page 2002

Show all 64 references
  1. [9]

    D., Steinke, T., Stemmer, U., and Ullman, J

    Bassily, R., Nissim, K., Smith, A. D., Steinke, T., Stemmer, U., and Ullman, J. R. Algorithmic stability for adaptive data analysis. SIAM J. Comput. , 50 0 (3), 2021. doi:10.1137/16M1103646. URL https://doi.org/10.1137/16M1103646

    2021 doi

  2. [10]

    Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds

    Beimel, A., Kaplan, H., Mansour, Y., Nissim, K., Saranurak, T., and Stemmer, U. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. CoRR, abs/2111.03980, 2021

    2021 arXiv

  3. [11]

    Adversarially robust streaming via dense-sparse trade-offs

    Ben - Eliezer, O., Eden, T., and Onak, K. Adversarially robust streaming via dense-sparse trade-offs. CoRR, abs/2109.03785, 2021 a

    2021 arXiv

  4. [12]

    P., and Yogev, E

    Ben - Eliezer, O., Jayaram, R., Woodruff, D. P., and Yogev, E. A framework for adversarially robust streaming algorithms. SIGMOD Rec. , 50 0 (1): 0 6--13, 2021 b

    2021

  5. [13]

    Optimal streaming and tracking distinct elements with high probability

    Blasiok, J. Optimal streaming and tracking distinct elements with high probability. ACM Trans. Algorithms , 16 0 (1): 0 3:1--3:28, 2020

    2020

  6. [14]

    and Shaw, J

    Boneh, D. and Shaw, J. Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory , 44 0 (5): 0 1897--1905, 1998. doi:10.1109/18.705568. URL https://doi.org/10.1109/18.705568

    1905 doi

  7. [15]

    Broder, A. Z. On the resemblance and containment of documents. In Proceedings of the Compression and Complexity of Sequences, pp.\ 21--29. IEEE, 1997

    1997

  8. [16]

    Broder, A. Z. Identifying and filtering near-duplicate documents. In Proc.of the 11th Annual Symposium on Combinatorial Pattern Matching, volume 1848 of LNCS, pp.\ 1--10. Springer, 2000

  9. [17]

    Finding frequent items in data streams

    Charikar, M., Chen, K., and Farach-Colton, M. Finding frequent items in data streams. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming, ICALP '02, pp.\ 693–703. Springer-Verlag, 2002. ISBN 3540438645

    2002

  10. [18]

    and Nelson, J

    Cherapanamjeri, Y. and Nelson, J. On adaptive distance estimation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020

    2020

  11. [19]

    Size-estimation framework with applications to transitive closure and reachability

    Cohen, E. Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences, 55: 0 441--453, 1997

    1997

  12. [20]

    Min-Hash Sketches, pp.\ 1--7

    Cohen, E. Min-Hash Sketches, pp.\ 1--7. Springer US, Boston, MA, 2008. ISBN 978-3-642-27848-8. doi:10.1007/978-3-642-27848-8_573-1. URL https://doi.org/10.1007/978-3-642-27848-8_573-1

    2008 doi

  13. [21]

    All-distances sketches, revisited: HIP estimators for massive graphs analysis

    Cohen, E. All-distances sketches, revisited: HIP estimators for massive graphs analysis. TKDE, 2015. URL http://arxiv.org/abs/1306.3284

    2015 arXiv

  14. [22]

    Stream sampling framework and application for frequency cap statistics

    Cohen, E. Stream sampling framework and application for frequency cap statistics. ACM Trans. Algorithms, 14 0 (4): 0 52:1--52:40, 2018. ISSN 1549-6325. doi:10.1145/3234338

    2018 doi

  15. [23]

    Sampling big ideas in query optimization

    Cohen, E. Sampling big ideas in query optimization. In Geerts, F., Ngo, H. Q., and Sintos, S. (eds.), Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023, Seattle, WA, USA, June 18-23, 2023 , pp.\ 361--371. ACM , 2023. doi:10....

    2023

  16. [24]

    and Geri, O

    Cohen, E. and Geri, O. Sampling sketches for concave sublinear functions of frequencies. In NeurIPS, 2019

    2019

  17. [26]

    and Lyu, X

    Cohen, E. and Lyu, X. The target-charging technique for privacy accounting across interactive computations. CoRR, abs/2302.11044, 2023 b . doi:10.48550/arXiv.2302.11044. URL https://doi.org/10.48550/arXiv.2302.11044

    2023 doi arXiv

  18. [27]

    On the robustness of countsketch to adaptive inputs

    Cohen, E., Lyu, X., Nelson, J., Sarl \' o s, T., Shechner, M., and Stemmer, U. On the robustness of countsketch to adaptive inputs. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022 a . URL https://arxiv.org/abs/2202.13736

    2022 arXiv

  19. [28]

    On the robustness of countsketch to adaptive inputs

    Cohen, E., Lyu, X., Nelson, J., Sarl \' o s, T., Shechner, M., and Stemmer, U. On the robustness of countsketch to adaptive inputs. In ICML , volume 162 of Proceedings of Machine Learning Research, pp.\ 4112--4140. PMLR , 2022 b

    2022

  20. [29]

    Tricking the hashing trick: A tight lower bound on the robustness of countsketch to adaptive inputs

    Cohen, E., Nelson, J., Sarlós, T., and Stemmer, U. Tricking the hashing trick: A tight lower bound on the robustness of countsketch to adaptive inputs. In Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023. doi:10.1609/aaai.v37i6.25882. URL http...

    2023 doi

  21. [30]

    One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches

    Cohen, E., Nelson, J., Sarl \'o s, T., Singhal, M., and Stemmer, U. One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches . arXiv preprint arXiv:2411.06370, 2024

    2024 arXiv

  22. [31]

    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 conference, pp.\ 265--284. Springer, 2006

    2006

  23. [32]

    N., and Vadhan, S

    Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., and Vadhan, S. On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pp.\ 381–390, New Yo...

    2009

  24. [33]

    Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., and Roth, A. L. Preserving statistical validity in adaptive data analysis. In STOC , pp.\ 117--126. ACM , 2015

    2015

  25. [34]

    and Steinke, T

    Feldman, V. and Steinke, T. Generalization for adaptively-chosen estimators via stable median. In COLT , volume 65 of Proceedings of Machine Learning Research, pp.\ 728--757. PMLR , 2017

    2017

  26. [35]

    and Zrnic, T

    Feldman, V. and Zrnic, T. Individual privacy accounting via a r\'enyi filter. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL https://openreview.net/forum?id=PBctz6_47ug

    2021

  27. [36]

    and Martin, G

    Flajolet, P. and Martin, G. N. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31: 0 182--209, 1985

    1985

  28. [37]

    Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm

    Flajolet, P., Fusy, E., Gandouet, O., and Meunier, F. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In Analysis of Algorithms (AofA). DMTCS, 2007

    2007

  29. [38]

    Freedman, D. A. A note on screening regression equations. The American Statistician, 37 0 (2): 0 152--155, 1983. doi:10.1080/00031305.1983.10482729. URL https://www.tandfonline.com/doi/abs/10.1080/00031305.1983.10482729

    1983 arXiv

  30. [39]

    Minimum cut in o(m log \( ^2 \) n) time

    Gawrychowski, P., Mozes, S., and Weimann, O. Minimum cut in o(m log \( ^2 \) n) time. In ICALP , volume 168 of LIPIcs, pp.\ 57:1--57:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020

    2020

  31. [40]

    J., Shlens, J., and Szegedy, C

    Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014

    2014 arXiv

  32. [41]

    BigQuery Documentation: Approximate Aggregate Functions , Accessed: 2024

    Google Cloud . BigQuery Documentation: Approximate Aggregate Functions , Accessed: 2024. URL https://cloud.google.com/bigquery/docs/reference/standard-sql/approximate_aggregate_functions. Google Cloud Documentation

    2024

  33. [42]

    P., Yu, H., and Zhou, S

    Gribelyuk, E., Lin, H., Woodruff, D. P., Yu, H., and Zhou, S. A strong separation for adversarially robust \( _0\) estimation for linear sketches. In Proceedings of the 65th Annual Symposium on Foundations of Computer Science (FOCS), 2024. URL https://arxiv.org/pdf/2409.16153

    2024 arXiv

  34. [43]

    Gutenberg, M. P. and Wulff-Nilsen, C. Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pp.\ 2542–2561, USA, 2020. Society for Industrial and Applied M...

    2020

  35. [44]

    and Rothblum, G

    Hardt, M. and Rothblum, G. N. A multiplicative weights mechanism for privacy-preserving data analysis. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA , pp.\ 61--70. IEEE Computer Society, 2010. doi:10.11...

    2010 doi

  36. [45]

    and Ullman, J

    Hardt, M. and Ullman, J. Preventing false discovery in interactive data analysis is hard. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 454--463. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.55. URL https://doi.ieeecomputersociety.org...

    2014 doi

  37. [46]

    and Woodruff, D

    Hardt, M. and Woodruff, D. P. How robust are linear sketches to adaptive inputs? In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, pp.\ 121–130, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290. doi:10.1145...

    2013

  38. [47]

    Adversarially robust streaming algorithms via differential privacy

    Hassidim, A., Kaplan, H., Mansour, Y., Matias, Y., and Stemmer, U. Adversarially robust streaming algorithms via differential privacy. In Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), 2020

    2020

  39. [48]

    HyperLogLog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm

    Heule, S., Nunkesser, M., and Hall, A. HyperLogLog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm. In EDBT, 2013

    2013

  40. [49]

    Ioannidis, J. P. A. Why most published research findings are false. PLoS Med, 0 (2): 0 8, 2005

    2005

  41. [50]

    M., Nelson, J., and Woodruff, D

    Kane, D. M., Nelson, J., and Woodruff, D. P. An optimal algorithm for the distinct elements problem. In PODS , pp.\ 41--52. ACM , 2010

    2010

  42. [51]

    The sparse vector technique, revisited

    Kaplan, H., Mansour, Y., and Stemmer, U. The sparse vector technique, revisited. In Belkin, M. and Kpotufe, S. (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA , volume 134 of Proceedings of Machine Learning Research, pp.\ 2747--2776....

    2021

  43. [52]

    Adaptive data analysis with correlated observations, 2022

    Kontorovich, A., Sadigurschi, M., and Stemmer, U. Adaptive data analysis with correlated observations, 2022

    2022

  44. [53]

    M., Burnham, K

    Lukacs, P. M., Burnham, K. P., and Anderson, D. R. Model selection bias and F reedman's paradox. Annals of the Institute of Statistical Mathematics, 62 0 (1): 0 117, 2009

    2009

  45. [54]

    Sketching in adversarial environments

    Mironov, I., Naor, M., and Segev, G. Sketching in adversarial environments. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pp.\ 651–660, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605580470. doi:10.1145/1374376...

    2008

  46. [55]

    B., and Swami, A

    Papernot, N., McDaniel, P., Goodfellow, I., Jha, S., Celik, Z. B., and Swami, A. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp.\ 506--519, 2017

    2017

  47. [56]

    Paterson, K. G. and Raynal, M. Hyperloglog: Exponentially bad in adversarial settings. Cryptology ePrint Archive, Paper 2021/1139, 2021. URL https://eprint.iacr.org/2021/1139. https://eprint.iacr.org/2021/1139

    2021

  48. [57]

    and Ting, D

    Reviriego, P. and Ting, D. Security of hyperloglog (HLL) cardinality estimation: Vulnerabilities and protection. IEEE Commun. Lett. , 24 0 (5): 0 976--980, 2020. doi:10.1109/LCOMM.2020.2972895. URL https://doi.org/10.1109/LCOMM.2020.2972895

    2020

  49. [58]

    Asymptotic theory for order sampling

    Ros \'e n, B. Asymptotic theory for order sampling. J. Statistical Planning and Inference, 62 0 (2): 0 135--158, 1997

    1997

  50. [59]

    and Roughgarden, T

    Roth, A. and Roughgarden, T. Interactive privacy via the median mechanism. In Schulman, L. J. (ed.), Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 , pp.\ 765--774. ACM , 2010. doi:10.1145/1806689.1806794. ...

    2010

  51. [60]

    and Even, S

    Shiloach, Y. and Even, S. An on-line edge-deletion problem. J. ACM, 28 0 (1): 0 1–4, jan 1981. ISSN 0004-5411. doi:10.1145/322234.322235. URL https://doi.org/10.1145/322234.322235

    1981

  52. [61]

    and Ullman, J

    Steinke, T. and Ullman, J. Interactive fingerprinting codes and the hardness of preventing false discovery. In Grünwald, P., Hazan, E., and Kale, S. (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp.\ 1588-...

    2015

  53. [62]

    Intriguing properties of neural networks

    Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013

    2013 arXiv

  54. [63]

    Vadhan, S. P. The complexity of differential privacy. In Lindell, Y. (ed.), Tutorials on the Foundations of Cryptography, pp.\ 347--450. Springer International Publishing, 2017. doi:10.1007/978-3-319-57048-8\_7. URL https://doi.org/10.1007/978-3-319-57048-8\_7

    2017 doi

  55. [64]

    Rounding Dynamic Matchings against an Adaptive Adversary

    Wajc, D. Rounding Dynamic Matchings against an Adaptive Adversary. Association for Computing Machinery, New York, NY, USA, 2020. URL https://doi.org/10.1145/3357713.3384258

    2020

  56. [65]

    Woodruff, D. P. and Zhou, S. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS) , 2021

    2021

Pith tools

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