Uniformity Testing over Hypergrids with Subcube Conditioning
Not on the map. Why?
Abstract (arXiv)
We give an algorithm for testing uniformity of distributions supported on hypergrids [m1] × cdots × [mn], which makes smashwidetildeO(poly(m)√n/ε2) many queries to a subcube conditional sampling oracle with m=maxi mi. When m is a constant, our algorithm is nearly optimal and strengthens the algorithm of [CCK+21] which has the same query complexity but works for hypercubes ± 1n only. A key technical contribution behind the analysis of our algorithm is a proof of a robust version of Pisier's inequality for functions over hypergrids using Fourier analysis.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 12 of its 39 references that are in the map. First posted on arXiv 17 Feb 2023.
Builds on
12 of 39 references.
References · 12
- 2013Optimal Algorithms for Testing Closeness of Discrete Distributionscited by 37
- 2015Optimal Testing for Properties of Distributionscited by 36
- 2016Testing Ising Modelscited by 23
- 2016Testing Bayesian Networkscited by 23
- 2014Testing Identity of Structured Distributionscited by 19
- 2019Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioningcited by 13
- 2020Learning and Testing Junta Distributions with Subcube Conditioningcited by 13
- 2020Downsampling for Testing and Learning in Product Distributionscited by 4
- 2020Testing Product Distributions: A Closer Lookcited by 4
- 2013An optimal lower bound for monotonicity testing over hypergridscited by 2
- 2017A o(d) · polylog~n Monotonicity Tester for Boolean Functions over the Hypergrid [n]dcited by 2
- 2021Linear Space Streaming Lower Bounds for Approximating CSPscited by 1
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.