mlsanityData to 7 Oct 2026

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

arXiv 1911.07357 ↗First posted 17 Nov 2019cs.DS cs.IT cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

We give a nearly-optimal algorithm for testing uniformity of distributions supported on -1,1n, which makes tilde O (√n/varepsilon2) queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on -1,1n, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Nov 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 2; 2024: 2; 2025: 4; 2026: 2.

13 papers.

Sort:

By area:

  1. 2025Optimal Inference Schedules for Masked Diffusion Modelscited by 25
  2. 2023Lifting uniform learners via distributional decompositioncited by 8
  3. 2024On the Computational Landscape of Replicable Learningcited by 7
  4. 2022Perfect Sampling from Pairwise Comparisonscited by 6
  5. 2022Complexity of High-Dimensional Identity Testing with Coordinate Conditional Samplingcited by 4
  6. 2022Gaussian Mean Testing Made Simplecited by 3
  7. 2025A Distributional-Lifting Theorem for PAC Learningcited by 3
  8. 2023Uniformity Testing over Hypergrids with Subcube Conditioningcited by 2
  9. 2025Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioningcited by 2
  10. 2025Sampling and Identity-Testing Without Approximate Tensorization of Entropycited by 1
  11. 2026Total Variation Distance Estimation in Autoregressive Modelscited by 1
  12. 2024Testing Credibility of Public and Private Surveys through the Lens of Regressioncited by 0
1 more
  1. 2026Testing Distributions Against Bounded Distinguisherscited by 0