A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data

By Liam Paninski. 2008

313 citations recorded by the source corpus.

Subfields: Mathematical Physics, Statistics and Probability

How researchers see this paper

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

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, methodology): “Then, the sample complexity of ( k, ε/ 3) -distribution testing must be at least When P is set to be Paninski’s perturbed family given in Eq.”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, methodology): “For constant δ, the sample complexity of (k, ε)-uniformity testing was shown to be Θ √ k/ε(2) in [40], [45], and the exact dependence on δ was later identified in [21], [35].”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “Following a long line of work, the optimal sample complexity for identity testing has been established as (k1/2/ε2) [33], [42], [46] under constant error probability.”
Minimax optimality of permutation tests (2020, methodology): “The `1 distance has an intuitive interpretation in terms of the total variation distance and has been considered as a metric for multinomial distribution testing (see e.g. Paninski, 2008; Chan et al., 2014; Diakonikolas and Kane, 2016; Balakrishnan and Wasserman, 2019, and also references therein).”
Introduction to Property Testing (2017, methodology): “23 Note (22)Recall that the alternatives include the testers of [221] and [73] or the collision probability test (of Algorithm 11.”
Property Testing For Differential Privacy (2018, background): “There is a large body of work exploring lower bounds and algorithmic upper bounds for tolerant testing using standard distances (TV, KL, χ 2 , etc.) with both a = 0 and a > 0 (Daskalakis et al., 2018, Paninski, 2008, Batu et al., 2013, Acharya et al., 2015, Valiant and Valiant, 2014).”
Priv'IT: Private and Sample Efficient Identity Testing (2017, methodology): “uot; for the case dTV(p;q) . The Paninski construction is a distribution where half the elements of the support have mass (1 + )=nand half have mass (1 )=n. We use this name for the construction as [Pan08] showed that this example is one of the hardest to distinguish from uniform: one requires ( p n”
An Automatic Inequality Prover and Instance Optimal Identity Testing (2014, methodology): “previous bound of O( √ n polylogn 4 ) from [5], and matching the tight bound on the number of samples required for testing the uniform distribution given in [13].”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, methodology): “Note that taking ζ to be uniform on {−1, 1}k/2, we retrieve the “Paninski construction” Paninski (2008), widely used to prove lower bounds in the centralized, unconstrained setting.”
Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “DP Le Cam’s method Le Cam’s method (Lemma 1 of Yu (1997)) is widely used to prove lower bounds for composite hypothesis testings such as uniformity testing (Paninski, 2008), density estimation (Yu, 1997; Ray and Schmidt-Hieber, 2018), and estimating functionals of distributions (Jiao et al.”
Hypothesis Testing for High-Dimensional Multinomials: A Selective Review (2017, methodology): “The global minimax separation rate was characterized in the works of Paninski (2008), Valiant and Valiant (2017).”
Hypothesis Testing For Densities and High-Dimensional Multinomials: Sharp Local Minimax Rates (2017, background): “This phenomenon is noted for instance in the work of [23].”
Estimating Renyi Entropy of Discrete Distributions (2014, background): “In particular, the Rényi entropy of order 2, H2(p), measures the quality of random number generators [19], [30], determines the number of unbiased bits that can be extracted from a physical source of randomness [6], [14], helps test graph expansion [8] and closeness of distributions [5], [34], and c”
Fisher Information Under Local Differential Privacy (2020, background): “That being said, Corollary 2 is valid over the same range of n values for which any existing lower bounds based on reduction to hypothesis testing with a hypercube or Paninski-type [25] hypothesis class can be valid.”