Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with distribution testing:
TR12-154 | 31st October 2012
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah

On the Power of Conditional Samples in Distribution Testing

Revisions: 1

In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, ... more >>>

TR13-111 | 17th August 2013
Gregory Valiant, Paul Valiant

Instance-by-instance optimal identity testing

We consider the problem of verifying the identity of a distribution: Given the description of a distribution over a discrete support $p=(p_1,p_2,\ldots,p_n)$, how many samples (independent draws) must one obtain from an unknown distribution, $q$, to distinguish, with high probability, the case that $p=q$ from the case that the total ... more >>>

TR14-156 | 26th November 2014
Jayadev Acharya, Clement Canonne, Gautam Kamath

A Chasm Between Identity and Equivalence Testing with Conditional Queries

Revisions: 1

A recent model for property testing of probability distributions enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain.
In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution $D$ (i.e., ... more >>>

TR15-063 | 15th April 2015
Clement Canonne

A Survey on Distribution Testing: Your Data is Big. But is it Blue?

Revisions: 1

The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, ... more >>>

TR16-015 | 4th February 2016
Oded Goldreich

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

Revisions: 3

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the ... more >>>

TR16-074 | 9th May 2016
Ilias Diakonikolas, Daniel Kane

A New Approach for Testing Properties of Discrete Distributions

We study problems in distribution property testing:
Given sample access to one or more unknown discrete distributions,
we want to determine whether they have some global property or are $\epsilon$-far
from having the property in $\ell_1$ distance (equivalently, total variation distance, or ``statistical distance'').
In this work, we give a ... more >>>

TR16-168 | 2nd November 2016
Eric Blais, Clement Canonne, Tom Gur

Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)

Revisions: 1

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method ... more >>>

TR16-177 | 11th November 2016
Ilias Diakonikolas, Daniel Kane, Alistair Stewart

Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures

Revisions: 1

We prove the first {\em Statistical Query lower bounds} for two fundamental high-dimensional learning problems involving Gaussian distributions: (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown mean Gaussian. In particular, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the ... more >>>

TR17-006 | 15th December 2016
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

Testing Ising Models

Revisions: 2

Given samples from an unknown multivariate distribution $p$, is it possible to distinguish whether $p$ is the product of its marginals versus $p$ being far from every product distribution? Similarly, is it possible to distinguish whether $p$ equals a given distribution $q$ versus $p$ and $q$ being far from each ... more >>>

TR17-075 | 29th April 2017
Clement Canonne, Ilias Diakonikolas, Alistair Stewart

Fourier-Based Testing for Families of Distributions

Revisions: 1

We study the general problem of testing whether an unknown discrete distribution belongs to a given family of distributions. More specifically, given a class of distributions $\mathcal{P}$ and sample access to an unknown distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and ... more >>>

TR17-132 | 7th September 2017
Ilias Diakonikolas, Daniel Kane, Alistair Stewart

Sharp Bounds for Generalized Uniformity Testing

We study the problem of {\em generalized uniformity testing}~\cite{BC17} of a discrete probability distribution: Given samples from a probability distribution $p$ over an {\em unknown} discrete domain $\mathbf{\Omega}$, we want to distinguish, with probability at least $2/3$, between the case that $p$ is uniform on some {\em subset} of $\mathbf{\Omega}$ ... more >>>

TR17-133 | 7th September 2017
Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

Sample-Optimal Identity Testing with High Probability

We study the problem of testing identity against a given distribution (a.k.a. goodness-of-fit) with a focus on the high confidence regime. More precisely, given samples from an unknown distribution $p$ over $n$ elements, an explicitly given distribution $q$, and parameters $0< \epsilon, \delta < 1$, we wish to distinguish, {\em ... more >>>

TR17-155 | 13th October 2017
Alessandro Chiesa, Tom Gur

Proofs of Proximity for Distribution Testing

Revisions: 1

Distribution testing is an area of property testing that studies algorithms that receive few samples from a probability distribution D and decide whether D has a certain property or is far (in total variation distance) from all distributions with that property. Most natural properties of distributions, however, require a large ... more >>>

TR18-002 | 31st December 2017
Constantinos Daskalakis, Gautam Kamath, John Wright

Which Distribution Distances are Sublinearly Testable?

Given samples from an unknown distribution $p$ and a description of a distribution $q$, are $p$ and $q$ close or far? This question of "identity testing" has received significant attention in the case of testing whether $p$ and $q$ are equal or far in total variation distance. However, in recent ... more >>>

ISSN 1433-8092 | Imprint