# Faster Algorithms for Testing under Conditional Sampling

arXiv: https://arxiv.org/abs/1504.04103 · HTML: https://mlsanity.com/paper/1504.04103/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2015.

## Built on by (most cited first, 7 of 7)

- [Lifting uniform learners via distributional decomposition](https://mlsanity.com/paper/2303.16208/) (2023)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Multi-Group Fairness Evaluation via Conditional Value-at-Risk Testing](https://mlsanity.com/paper/2312.03867/) (2023)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Sampling and Identity-Testing Without Approximate Tensorization of Entropy](https://mlsanity.com/paper/2506.23456/) (2025)
- [Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction](https://mlsanity.com/paper/2608.06262/) (2026)

## Abstract (arXiv)

There has been considerable recent interest in distribution-tests whose run-time and sample requirements are sublinear in the domain-size k. We study two of the most important tests under the conditional-sampling model where each query specifies a subset S of the domain, and the response is a sample drawn from S according to the underlying distribution. For identity testing, which asks whether the underlying distribution equals a specific given distribution or ε-differs from it, we reduce the known time and sample complexities from tildeO(ε-4) to tildeO(ε-2), thereby matching the information theoretic lower bound. For closeness testing, which asks whether two distributions underlying observed data sets are equal or different, we reduce existing complexity from tildeO(ε-4 log5 k) to an even sub-logarithmic tildeO(ε-5 log log k) thus providing a better bound to an open problem in Bertinoro Workshop on Sublinear Algorithms [Fisher, 2004].