Uniformity Testing over Hypergrids with Subcube Conditioning

Publication date 17 February 2023

Abstract: We give an algorithm for testing uniformity of distributions supported on hypergrids

[m]^{n}

, which makes

i l d e O (e x t p o l y (m) s q r t n / e p s i l o n^{2})

queries to a subcube conditional sampling oracle. When the side length

m

of the hypergrid 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

{p m 1}^{n}

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

m a t h b b Z_{m}^{n}

using Fourier analysis.

This page was built for publication: Uniformity Testing over Hypergrids with Subcube Conditioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426825)