The uniform distribution is complete with respect to testing identity to a fixed distribution

By Oded Goldreich. 2016

73 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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 Artificial Intelligence

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “result of [29] provides a formal reduction of arbitrary q to the uniform distribution case.”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, methodology): “Towards this, we rely on the following result of [28], which we state here for completeness.”
Test without Trust: Optimal Locally Private Distribution Testing (2018, methodology): “We remark that it is easy to extend our uniformity testing results to the more general problem of identity testing using a reduction argument from Goldreich [23].”
Communication and Memory Efficient Testing of Discrete Distributions (2019, methodology): “The reduction of identity to uniformity in Goldreich (2016) immediately translates our upper bounds from uniformity to identity.”
Introduction to Property Testing (2017, background): “, testing equality to a known distribution) to testing the uniform distribution; this reduction appeared in [137].”
Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, methodology): “In recent work [19], Goldreich provides a reduction from identity testing to uniformity testing with only a constant multiplicative overhead in the query complexity.”
Two Party Distribution Testing: Communication and Security (2018, methodology): “For the closeness testing problem, in addition to the aforementioned references, we highlight the result of [DK16] (see also [Gol16]), whose techniques are the starting point of our protocols.”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, methodology): “This line of work culminated in efficient and sample-optimal testing algorithms (Paninski, 2008; Valiant and Valiant, 2017; Acharya et al., 2015; Goldreich, 2016; Diakonikolas et al., 2018); we refer the reader to the surveys (Rubinfeld, 2012; Canonne, 2015; Balakrishnan and Wasserman, 2018), as wel”
Distributed Uniformity Testing (2018, background): “Uniformity testing is especially interesting because in the centralized setting, it is known that for any fixed distribution μ, the problem of testing equality to μ can be reduced to uniformity testing [10, 15].”