All reports by Author Gautam Kamath:

__
TR18-131
| 17th July 2018
__

Gautam Kamath, Christos Tzamos#### Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing

__
TR18-002
| 31st December 2017
__

Constantinos Daskalakis, Gautam Kamath, John Wright#### Which Distribution Distances are Sublinearly Testable?

__
TR17-006
| 15th December 2016
__

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath#### Testing Ising Models

Revisions: 2

__
TR14-156
| 26th November 2014
__

Jayadev Acharya, Clement Canonne, Gautam Kamath#### A Chasm Between Identity and Equivalence Testing with Conditional Queries

Revisions: 2

Gautam Kamath, Christos Tzamos

We investigate distribution testing with access to non-adaptive conditional samples.

In the conditional sampling model, the algorithm is given the following access to a distribution: it submits a query set $S$ to an oracle, which returns a sample from the distribution conditioned on being from $S$.

In the non-adaptive setting, ...
more >>>

Constantinos Daskalakis, Gautam Kamath, John Wright

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 >>>

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

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 >>>

Jayadev Acharya, Clement Canonne, Gautam Kamath

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 >>>