Pith. sign in

REVIEW 1 major objections 4 minor 47 references

Is Randomness Necessary for Adaptive Data Analysis?

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

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

Pith's one-line read Randomness is strictly necessary for adaptive data analysis: every deterministic mechanism can be forced to fail after only O(n log n) adaptively chosen queries.

desk verdict Deterministic mechanisms fail after O(n log n) adaptive queries against unbounded analysts; the proof is sound on my reading, with one deferred lemma and one wording slip to fix. read the letter →

arxiv 2607.07085 v2 pith:R3KMK7WN submitted 2026-07-08 cs.CR cs.DScs.LG

Edith Cohen , Haim Kaplan , Yishay Mansour , Shay Sapir , Uri Stemmer This is my paper · ORCID
classification cs.CRcs.DScs.LG
keywords adaptivedataanalysisdeterministicmechanismsrandomnesslowerboundsstatisticalqueriesrandomoraclemodeloverfittingRamsey-theoreticextractionpseudorandomgenerators
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 asks whether randomness is inherent to adaptive data analysis, where a mechanism repeatedly answers statistical queries chosen based on previous answers. It proves that in the information-theoretic setting, against a computationally unbounded analyst, randomness is strictly necessary: every deterministic mechanism can be forced to err after only k = O(n log n) adaptively chosen queries, while randomized mechanisms can answer roughly n^2 queries. The proof first defeats deterministic natural mechanisms with a search-by-halving attack on threshold queries, then lifts the attack to all deterministic mechanisms in the random oracle model using masked queries and dynamic pointers, and finally removes the oracle using a Ramsey-theoretic construction that forces deterministic mechanisms to behave like natural ones. A complementary result formalizes that randomness is not necessary when the analyst is computationally bounded, assuming pseudorandom generators exist. The paper settles a decade-old open question about the role of randomness in preventing overfitting.

What carries the argument

The engine is a search-by-halving attack that maintains a set of surviving datasets consistent with the transcript and in each round produces a separating threshold query, a binary query for which every valid answer rules out a constant fraction of those datasets. For general mechanisms, the random-oracle version uses random masks derived from oracle bits at fresh pointer offsets, where a dynamic pointer supplies independent mask refreshes each round; the plain-model version replaces oracle freshness with an order-type Ramsey extraction that gives a large homogeneous set on which any deterministic mechanism's one-bit discretized answers are invariant under weak order type, forcing it to beha

What would settle it

A deterministic mechanism that stays 0.1-accurate for more than O(n log n) adaptive queries against an unbounded analyst in the plain model would refute the main theorem. Concretely, one can look for a mechanism whose discretized answer changes when a query parameter is swapped from an a-point to its adjacent b-point while the sample does not contain that a-point; the Ramsey extraction says this cannot happen, so finding such a mechanism would falsify the lower bound.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.5 / 5.7: for every deterministic mechanism there exists a domain, a target distribution, and a computationally unbounded analyst such that the mechanism is forced to answer some queried value with error greater than 0.1 within k = O(n log n) adaptive rounds, with probability 1 - o(1) over the sample. In the random oracle model, the same failure is proven for every deterministic mechanism, and more generally for mechanisms using at most r random bits, within O(n + r) rounds. The paper also proves the folklore converse: assuming pseudorandom generators exist, deterministic mechanisms can match the ~n^2 query bound against computationally bounded analysts, so rand

Load-bearing premise

In the plain model, the attack assumes that on a huge specially chosen domain, any deterministic mechanism's yes/no answers depend only on the relative order of the points and parameters it sees, not on which specific values are swapped; if that invariance fails, the O(n log n) bound collapses.

Editorial extensions

If this is right

  • Against a computationally unbounded analyst, no deterministic mechanism can answer more than O(n log n) adaptively chosen statistical queries with constant accuracy; randomness is provably necessary for a super-linear query count.
  • Randomized mechanisms continue to support ~n^2 queries, so the separation is tight in the sense that deterministic mechanisms lose the quadratic regime.
  • Mechanisms with fewer than quadratic private random bits remain vulnerable: in the random oracle model any mechanism with r random bits can be defeated in O(n + r) queries; only ~n^2 random bits suffice for the quadratic bound.
  • Under standard cryptographic assumptions, randomness is not necessary in practice against bounded analysts: deterministic PRG-based mechanisms match randomized ones, so the necessity appears only in the information-theoretic regime.
  • The adversarial distributions used in the plain-model lower bound have tower-type domains and enormous query descriptions, making the result a separation of information-theoretic power rather than a practical attack.

Reading between the lines

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

  • Inference: The search-by-halving attack isolates a dataset the way binary search isolates a hidden item; a natural extension is to ask whether other interactive estimation problems admit analogous deterministic-versus-random separations whenever a naturalness or invariance property can be enforced.
  • Inference: The Ramsey-theoretic step trades domain size for randomness; this suggests further questions about how large a domain must be to make randomness unnecessary, or about quantitatively trading private random bits against domain size.
  • Inference: The bounded-analyst positive result depends on the existence of pseudorandom generators; if such generators do not exist for a given object, the deterministic quadratic simulation collapses, so the boundary between bounded and unbounded analysts could be redrawn under complexity assumptions.
  • Inference: A testable empirical analog would run the natural-mechanism attack on finite data with simple deterministic predictors; the halving argument predicts that an adaptive analyst can drive any deterministic empirical-risk minimizer to visible overfitting in about n log n rounds.
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

1 major / 4 minor

Summary. The paper asks whether randomness is necessary for Adaptive Data Analysis when the analyst is computationally unbounded. It claims a strong separation: deterministic mechanisms can be forced to fail after k = O(n log n) adaptively chosen queries, whereas randomized mechanisms support about n^2 queries. The proof has three parts: (1) a halving attack against deterministic natural mechanisms using threshold queries (Lemma 3.1, Theorem 3.3); (2) a random-oracle-model attack that enforces natural behavior via fresh mask blocks and pointer ranges, with explicit union bounds (Lemma 4.5, Claims 4.6–4.9, Theorem 4.10), extended to mechanisms with r random bits (Theorem 4.11); and (3) a plain-model reduction based on order-type Ramsey extraction that forces a 'bit-natural' behavior for arbitrary deterministic mechanisms over a tower-type domain (Lemma 5.2, Theorems 5.3 and 5.7). The paper also formalizes the folklore positive result for computationally bounded analysts using PRGs (Appendix A).

Significance. If correct, this is a significant result: it closes a long-standing open question about the role of randomness in ADA, showing that in the information-theoretic setting a super-linear number of adaptive queries provably requires internal randomness. The random-oracle attack is technically substantial and includes detailed probability accounting and a non-trivial finite-pointer replacement. The plain-model Ramsey construction is elegant and makes the lower bound model-independent, although at the cost of a tower-type domain. The limited-randomness extension is plausible. The main weakness is that the plain-model proof currently rests on Lemma 5.6, whose proof is only asserted as analogous to Lemma 3.1; this lemma is load-bearing for Theorem 5.7.

major comments (1)
  1. [§5.3, Lemma 5.6 / Theorem 5.7] Lemma 5.6 is the engine of the plain-model separation, but it is asserted with only 'The proof is analogous to Lemma 3.1.' The adaptation is not literally identical: Lemma 3.1 uses that non-containing datasets return the same real answer for neighboring threshold queries, whereas Lemma 5.5 only guarantees the same discretized bit. The proof must show that this still implies a real-valued separating query (no real answer value exceeds 9/10 of H_T), and must handle the terminal case |H_T|=1, where bit-naturalness forces the same bit for q_S and q_all although accuracy forces opposite bits. Please supply a complete formal proof and derive the n^{-8} probability (presumably from the collision-free sample) in Theorem 5.7.
minor comments (4)
  1. [§5.2, Theorem 5.3] The coloring χ(w) is said to use 'at most 2^k colors,' but the length of the 'j-bit string' varies with the largest legal j. This can be fixed by padding to length k with zeros; please state this explicitly and spell out why the appended-suffix argument for j<k preserves the same weak order type and the same largest legal index.
  2. [§4.3, Theorem 4.11] The statement calls the mechanism 'deterministic' while allowing r private random bits; rephrase as 'with r random bits.' The proof sketch for the limited-randomness extension is very brief; adding the formal 2^r accounting in H_T, R, and Lprev would help.
  3. [Lemma 5.5] The condition 'x^i_{j,a} ∉ S' is an abuse of notation: S is a set of k-tuples over [M]. It should mean that x^i_{j,a} does not appear as any coordinate of any point in S.
  4. [§4.2, Theorem 4.10] The reduction to M_mask does not track the constant overhead in running time and query-evaluation time. Also, for t smaller than the pointer length the mechanism cannot read the pointer; state the intended regime (or define how the mechanism accesses the input) so that the bound O(nN log N + log t) is meaningful.

Circularity Check

0 steps flagged · score 1.0 of 10

No material circularity: the lower-bound proofs are self-contained counting/union-bound/Ramsey arguments; the only flagged gap (deferred proof of Lemma 5.6) is a proof-completeness issue, not a circular reduction.

full rationale

The central derivation chain is not circular. The natural-mechanism lower bound (Lemma 3.1) is a table/threshold argument from the accuracy definition, with no quantity fitted to data. The masked-mechanism result (Lemma 3.4) is a black-box reduction to Lemma 3.1 via a fixed mask v and a pigeonhole argument; it does not define its conclusion into its premise. The random-oracle results (Claims 4.6-4.9, Theorem 4.10) are supported by explicit union bounds over datasets, masked-query sequences, and pointer histories; the pointer range R is chosen to make the failure probability δ, and the 'long-pointer' idealization is later removed by a counting argument. The plain-model result (Theorems 5.3 and 5.7) rests on the order-type Ramsey extraction (Lemma 5.2, proven in Appendix B from the classical Ramsey theorem) and on Lemma 5.5, which shows by an order-type comparison that out-of-sample query changes do not alter the discretized answer. No quoted equation equates the target result with its input by construction. The self-citations that appear — [BNS+16], [Bla23], [Ste16] — are used as external anchors (randomized quadratic upper bounds, folklore) rather than as the premise of the new lower bounds; [BNS+16] has overlapping authors but is an established, independently checkable result, and [Ste16] is explicitly proved in Appendix A. The one genuinely flagged issue is Section 5's Lemma 5.6: the paper only says 'The proof is analogous to the proof of Lemma 3.1' and does not write out the reduction. Because 'bit-natural' is weaker than real-valued naturalness, this omission is a real verification gap, but it is an omitted proof, not a circular step: nothing in the text forces the target bound to be equal to an assumption. Accordingly, the circularity score is minimal and reflects only this presentational gap and minor self-citation, not a load-bearing circularity.

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

The ledger is dominated by proof-parameter and modeling choices, not by fitted data parameters. N, δ, R, and M are chosen by hand to make the adversarial construction work. There are no new physical or computational entities introduced: the mask, random oracle, and bit-natural mechanism are proof devices, not postulated entities with independent empirical handles.

free parameters (5)
  • domain size N = N = n^10
    Chosen so that an n-sample from the uniform distribution over [N] is a set with high probability; this makes the common-points counting argument in Lemma 3.1 work and sets the query bound k = O(n log N).
  • accuracy/success constants = ε = 0.1, success probability 9/10
    Standard constants inherited from Definition 2.2 of ε-accuracy; not fitted to data but part of the ADA framework.
  • failure probability δ = δ = N^{-6}
    Set in Lemma 4.5; any inverse-polynomial-in-N choice would work. Used to make union-bound failure probabilities negligible.
  • pointer range R = R = δ^{-1} N n 2^{Nk} E^k k t
    Chosen large enough so that, with probability at least 1-δ, the mechanism never reads an out-of-sample mask location in any of the N^n datasets, 2^{Nk} masked-query sequences, and E^k pointer sequences considered.
  • Ramsey domain size M = M ≥ R_ord^{rmax}(2Nk, 2^k)
    Tower-type size required by the order-type Ramsey theorem in the plain model; makes the query descriptions astronomically large, which is an explicit caveat of Theorem 1.5.
assumptions (5)
  • standard math Order-type Ramsey theorem
    Used in Lemma 5.2 and Appendix B to extract a homogeneous set D on which a deterministic mechanism's discretized outputs depend only on weak order type. This is standard finite Ramsey theory, not proved in the paper.
  • domain assumption Existence of pseudorandom generators
    Assumed in Observation 1.1 and Appendix A for the positive result about computationally bounded analysts. The negative results do not depend on PRGs.
  • domain assumption Random oracle model
    Theorem 1.2 and Section 4 assume both analyst and mechanism share a public random oracle O. This is a modeling assumption; Section 5 removes it at the price of tower-type domains.
  • domain assumption Sample without collisions under uniform [N]
    Section 3 assumes N = n^10 so that an n-sample is a set rather than a multiset with high probability; this is a standard and harmless modeling step for lower bounds.
  • domain assumption Mechanism running time t is large enough to read pointer descriptions
    Lemma 4.5/Theorem 4.10 require pointers of length O(nN log N + log t). For the result to be non-vacuous, t must be large enough for the mechanism to read those pointers; the paper notes this is satisfied for polynomial-in-input-length t.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Is Randomness Necessary for Adaptive Data Analysis?." pith.science (2026). https://pith.science/paper/R3KMK7WN

@misc{pith2026260707085,
  author       = {Pith},
  title        = {Pith review of: Is Randomness Necessary for Adaptive Data Analysis?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R3KMK7WN}},
  note         = {Machine review of arXiv:2607.07085}
}
abstract

The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a dataset containing $n$ i.i.d.\ samples from an unknown distribution $P$ over a domain $X$, and our goal is to answer a sequence of $k$ adaptively chosen statistical queries with respect to $P$. The main question is how many queries we can support (i.e., how large $k$ can be), primarily as a function of the number of samples $n$. This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support $k \approx n^2$ queries, and no computationally efficient mechanism can answer $k \gg n^2$ queries. In this paper, we address a fundamental question: is randomness necessary for ADA? Despite a decade of work on ADA, this question remains open. A folklore observation dating back to the initial works on ADA is that randomness is {\em not} necessary when the analyst is computationally bounded. Yet, the necessity of randomness against computationally unbounded analysts has remained elusive. Our main contribution resolves this gap in the information-theoretic setting. Perhaps surprisingly, we show that randomness is strictly necessary to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just $k = \tilde{O}(n)$ queries.

Figures

Figures reproduced from arXiv: 2607.07085 by the authors.

Figure 1
Figure 1. Example of an |HT |×(N+1) table. In this example, when the input dataset is S2 and the query is qj , the mechanism M returns the answer 0.74. Datasets in H T S|HT | ≈ 0 . . . . . . 0.71 0.71 . . . ≈ 1 S|HT |-1 ≈ 0 . . . . . . 0.77 0.77 . . . ≈ 1 S|HT |-2 ≈ 0 . . . . . . 0.75 0.75 . . . ≈ 1 S|HT |-3 ≈ 0 . . . . . . 0.69 0.76 . . . ≈ 1 S|HT |-4 ≈ 0 . . . . . . 0.68 0.68 . . . ≈ 1 . . . . . . . . . . . . . . . . . . . … view at source ↗
Figure 2
Figure 2. Extending the table from [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 1 linked inside Pith

  1. [1]

    The space complexity of approximating the frequency moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pages 20--29, 1996

    1996

  2. [2]

    Queries and concept learning

    Dana Angluin. Queries and concept learning. Machine learning , 2(4):319--342, 1988

    1988

  3. [3]

    Separations between oblivious and adaptive adversaries for natural dynamic graph problems

    Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, and Thatchaphol Saranurak. Separations between oblivious and adaptive adversaries for natural dynamic graph problems. In SODA , pages 5669--5687. SIAM , 2026

    2026

  4. [4]

    Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries

    MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2677--2727. SIAM, 2023

    2023

  5. [5]

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

    Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In STOC , pages 1671--1684. ACM , 2022

    2022

  6. [6]

    Subsampling suffices for adaptive data analysis

    Guy Blanc. Subsampling suffices for adaptive data analysis. In STOC , pages 999--1012. ACM , 2023

    2023

  7. [7]

    Chosen ciphertext attacks against protocols based on the rsa encryption standard pkcs\# 1

    Daniel Bleichenbacher. Chosen ciphertext attacks against protocols based on the rsa encryption standard pkcs\# 1. In Annual international cryptology conference , pages 1--12. Springer, 1998

    1998

  8. [8]

    Smith, Thomas Steinke, Uri Stemmer, and Jonathan R

    Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. In STOC , pages 1046--1059. ACM , 2016

    2016

Show all 47 references
  1. [9]

    Another advantage of free choice (extended abstract) completely asynchronous agreement protocols

    Michael Ben-Or. Another advantage of free choice (extended abstract) completely asynchronous agreement protocols. In Proceedings of the second annual ACM symposium on Principles of distributed computing , pages 27--30, 1983

    1983

  2. [10]

    Random oracles are practical: A paradigm for designing efficient protocols

    Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security , pages 62--73, 1993

    1993

  3. [11]

    Strong fooling sets for multi-player communication with applications to deterministic estimation of stream statistics

    Amit Chakrabarti and Sagar Kale. Strong fooling sets for multi-player communication with applications to deterministic estimation of stream statistics. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 41--50. IEEE, 2016

    2016

  4. [12]

    Finding missing items requires strong forms of randomness

    Amit Chakrabarti and Manuel Stoeckl. Finding missing items requires strong forms of randomness. In CCC , volume 300 of LIPIcs , pages 28:1--28:20. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

    2024

  5. [13]

    Generalization in adaptive data analysis and holdout reuse

    Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In NeurIPS , pages 2350--2358, 2015

    2015

  6. [14]

    Preserving statistical validity in adaptive data analysis

    Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In STOC , pages 117--126. ACM , 2015

    2015

  7. [15]

    Woodruff, and Samson Zhou

    Itai Dinur, Uri Stemmer, David P. Woodruff, and Samson Zhou. On differential privacy and adaptive data analysis with bounded space. In EUROCRYPT (3) , volume 14006 of Lecture Notes in Computer Science , pages 35--65. Springer, 2023

    2023

  8. [16]

    Impossibility of distributed consensus with one faulty process

    Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM) , 32(2):374--382, 1985

    1985

  9. [17]

    Probabilistic counting algorithms for data base applications

    Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applications. Journal of computer and system sciences , 31(2):182--209, 1985

    1985

  10. [18]

    Benjamin Fish, Lev Reyzin, and Benjamin I. P. Rubinstein. Sublinear-time adaptive data analysis. In ISAIM , 2018

    2018

  11. [19]

    How to prove yourself: Practical solutions to identification and signature problems

    Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO , volume 263 of Lecture Notes in Computer Science , pages 186--194. Springer, 1986

    1986

  12. [20]

    Generalization for adaptively-chosen estimators via stable median

    Vitaly Feldman and Thomas Steinke. Generalization for adaptively-chosen estimators via stable median. In COLT , volume 65 of Proceedings of Machine Learning Research , pages 728--757. PMLR , 2017

    2017

  13. [21]

    Calibrating noise to variance in adaptive data analysis

    Vitaly Feldman and Thomas Steinke. Calibrating noise to variance in adaptive data analysis. In COLT , volume 75 of Proceedings of Machine Learning Research , pages 535--544. PMLR , 2018

    2018

  14. [22]

    Sketching and streaming entropy via approximation theory

    Nicholas JA Harvey, Jelani Nelson, and Krzysztof Onak. Sketching and streaming entropy via approximation theory. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages 489--498. IEEE, 2008

    2008

  15. [23]

    Moritz Hardt and Jonathan R. Ullman. Preventing false discovery in interactive data analysis is hard. In FOCS , pages 454--463. IEEE Computer Society, 2014

    2014

  16. [24]

    A new analysis of differential privacy's generalization guarantees

    Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi - Malvajerdi, and Moshe Shenfeld. A new analysis of differential privacy's generalization guarantees. In ITCS , volume 151 of LIPIcs , pages 31:1--31:17. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020

    2020

  17. [25]

    Separating adaptive streaming from oblivious streaming using the bounded storage model

    Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. In Annual International Cryptology Conference , pages 94--121. Springer, 2021

    2021

  18. [26]

    A simple proof of a new set disjointness with applications to data streams

    Akshay Kamath, Eric Price, and David P Woodruff. A simple proof of a new set disjointness with applications to data streams. arXiv preprint arXiv:2105.11338 , 2021

    2021 arXiv

  19. [27]

    The probabilistic communication complexity of set intersection

    Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics , 5(4):545--557, 1992

    1992

  20. [28]

    Adaptive data analysis with correlated observations

    Aryeh Kontorovich, Menachem Sadigurschi, and Uri Stemmer. Adaptive data analysis with correlated observations. In ICML , volume 162 of Proceedings of Machine Learning Research , pages 11483--11498. PMLR , 2022

    2022

  21. [29]

    Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm

    Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning , 2(4):285--318, 1988

    1988

  22. [30]

    On the advantages of free choice: A symmetric and fully distributed solution to the dining philosophers problem

    Daniel Lehmann and Michael O Rabin. On the advantages of free choice: A symmetric and fully distributed solution to the dining philosophers problem. In Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages , pages 133--138, 1981

    1981

  23. [31]

    A necessary and sufficient stability notion for adaptive generalization

    Katrina Ligett and Moshe Shenfeld. A necessary and sufficient stability notion for adaptive generalization. In NeurIPS , pages 11481--11490, 2019

    2019

  24. [32]

    Fingerprinting codes meet geometry: Improved lower bounds for private query release and adaptive data analysis

    Xin Lyu and Kunal Talwar. Fingerprinting codes meet geometry: Improved lower bounds for private query release and adaptive data analysis. In STOC , pages 2374--2385. ACM , 2025

    2025

  25. [33]

    A chosen ciphertext attack on rsa optimal asymmetric encryption padding (oaep) as standardized in pkcs\# 1 v2

    James Manger. A chosen ciphertext attack on rsa optimal asymmetric encryption padding (oaep) as standardized in pkcs\# 1 v2. 0. In Annual international cryptology conference , pages 230--238. Springer, 2001

    2001

  26. [34]

    Smith, Thomas Steinke, Uri Stemmer, and Jonathan R

    Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. The limits of post-selection generalization. In NeurIPS , pages 6402--6411, 2018

    2018

  27. [35]

    Adaptive data analysis in a balanced adversarial model

    Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia. Adaptive data analysis in a balanced adversarial model. In NeurIPS , 2023

    2023

  28. [36]

    Searching games with errors—fifty years of coping with liars

    Andrzej Pelc. Searching games with errors—fifty years of coping with liars. Theoretical Computer Science , 270(1-2):71--109, 2002

    2002

  29. [37]

    Frank P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society , 30(1):264--286, 1930

    1930

  30. [38]

    Tight bounds for answering adaptively chosen concentrated queries

    Emma Rapoport, Edith Cohen, and Uri Stemmer. Tight bounds for answering adaptively chosen concentrated queries. CoRR , abs/2507.13700, 2025

    2025

  31. [39]

    Rivest, Albert R

    Ronald L. Rivest, Albert R. Meyer, Daniel J. Kleitman, Karl Winklmann, and Joel Spencer. Coping with errors in binary search procedures. Journal of Computer and System Sciences , 20(3):396--404, 1980

    1980

  32. [40]

    Rogers, Aaron Roth, Adam D

    Ryan M. Rogers, Aaron Roth, Adam D. Smith, and Om Thakkar. Max-information, differential privacy, and post-selection hypothesis testing. In FOCS , pages 487--494. IEEE Computer Society, 2016

    2016

  33. [41]

    Controlling bias in adaptive data analysis using information theory

    Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In AISTATS , volume 51 of JMLR Workshop and Conference Proceedings , pages 1232--1240. JMLR.org, 2016

    2016

  34. [42]

    Generalization in the face of adaptivity: A bayesian perspective

    Moshe Shenfeld and Katrina Ligett. Generalization in the face of adaptivity: A bayesian perspective. In NeurIPS , 2023

    2023

  35. [43]

    Individuals and privacy in the eye of data analysis

    Uri Stemmer. Individuals and privacy in the eye of data analysis . PhD thesis, Ben-Gurion University of the Negev, 2016

    2016

  36. [44]

    Streaming algorithms for the missing item finding problem

    Manuel Stoeckl. Streaming algorithms for the missing item finding problem. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 793--818. SIAM, 2023

    2023

  37. [45]

    Thomas Steinke and Jonathan R. Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. In COLT , volume 40 of JMLR Workshop and Conference Proceedings , pages 1588--1628. JMLR.org, 2015

    2015

  38. [46]

    Reasoning about generalization via conditional mutual information

    Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In COLT , volume 125 of Proceedings of Machine Learning Research , pages 3437--3452. PMLR , 2020

    2020

  39. [47]

    Some complexity questions related to distributive computing (preliminary report)

    Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the eleventh annual ACM symposium on Theory of computing , pages 209--213, 1979

    1979

Pith tools

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