Taming big probability distributions

By Ronitt Rubinfeld. 2012

103 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, methodology): “We refer the reader to surveys [7], [15], [18], [43] for a comprehensive review of recent results on discrete distribution learning and testing.”
Distributed Simulation and Distributed Inference (2018, methodology): “We point out that the above formulation encompasses both density and parameter estimation, as well as distribution testing (see e.g. [Rub12, Can15] and [Gol17] for a survey of property and distribution testing).”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “setting of interest to us has received a lot of attention in the past decade, especially in the computer science literature; see [8], [17], [41] for surveys.”
Communication Complexity of Statistical Distance (2018, background): “(For results about the complexity of other problems where the inputs are black-box samples from distributions, see the surveys [8, 15, 25].)”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “In this section, we only focus on closely related papers and we refer an interested reader to surveys and books [13], [21], [34], [43] for a comprehensive treatment.”
Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, background): “…sample complexity of our private closeness tester is Related Work During the past two decades, distribution property testing [3] – whose roots lie in statistical hypothesis testing [23, 22] – has received considerable attention by the computer science community, see [25, 7] for two recent surveys.”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, background): “Tight upper and lower bounds on the sample complexity have been obtained for properties such as uniformity, identity to a speciﬁed distribution, monotonicity, and many more (see references above, or [46, 18] for surveys).”
Communication and Memory Efficient Testing of Discrete Distributions (2019, background): “The field of distribution property testing Batu et al. (2000) has been extensively investigated in the past couple of decades, see, e.g., the surveys Rubinfeld (2012); Canonne (2015); Goldreich (2017).”
An Automatic Inequality Prover and Instance Optimal Identity Testing (2014, unknown): “Also see [15] for a recent survey.”
Testing Identity of Structured Distributions (2014, background): “ptotically fewer than the support size n, and ideally much less than that. See [GR00, BFR+00, BFF+01, Bat01, BDKR02, BKR04, Pan08, Val11, VV11, DDS+13, ADJ+11, LRR11, ILR12] for a sample of works and [Rub12] for a survey. One of the ﬁrst problems studied in this line of work is that of “identity tes”
Hypothesis Testing for High-Dimensional Multinomials: A Selective Review (2017, methodology): “…theory and theoretical computer science and we provide an overview of some important results from these different communities in this paper.2 2Theoretical computer science centric surveys of a subset of these results include the papers Rubinfeld (2012), Goldreich (2017) and Canonne (2018).”
Differentially Private Identity and Equivalence Testing of Discrete Distributions (2018, background): “…two decades, distribution property testing (Batu et al., 2000) – whose roots lie in statistical hypothesis testing (Neyman & Pearson, 1933; Lehmann & Romano, 2005) – has received considerable attention by the computer science community, see (Rubinfeld, 2012; Canonne, 2015) for two recent surveys.”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, methodology): “…line of work culminated in efﬁcient and sample-optimal testing algorithms [Pan08, VV17, ADK15, Gol16, DGPP18]; we refer the reader to the surveys [Rub12, Can15, BW18], as well as the recent book [Gol17] (Chapter 11) for further details on identity testing, and the more general ﬁeld of…”
Optimal Algorithms for Testing Closeness of Discrete Distributions (2013, background): “Estimating properties of distributions using samples is a classical topic in statistics that has received considerable attention in the theoretical CS community during the past decade; see [GR00, BFR00, BFF01, Bat01, BDKR02, BKR04, Pan08, Val08, Ona09, Val11, VV11a, VV11b, DDS13, Rub12, BNNR11, ADJ1”