Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
Preprint
Abstract
We study monotonicity testing of high-dimensional distributions on $\{-1,1\}^n$ in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio~\cite{CRS15} and Bhattacharyya and Chakraborty~\cite{BC18}. Previous work shows that the \emph{sample complexity} of monotonicity testing must be exponential in $n$ (Rubinfeld, Vasilian~\cite{RV20}, and Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee~\cite{AGPRY19}). We show that the subcube \emph{query complexity} is $\tildeΘ(n/\varepsilon^2)$, by proving nearly matching upper and lower bounds. Our work is the first to use directed isoperimetric inequalities (developed for function monotonicity testing) for analyzing a distribution testing algorithm. Along the way, we generalize an inequality of Khot, Minzer, and Safra~\cite{KMS18} to real-valued functions on $\{-1,1\}^n$. We also study uniformity testing of distributions that are promised to be monotone, a problem introduced by Rubinfeld, Servedio~\cite{RS09} , using subcube conditioning. We show that the query complexity is $\tildeΘ(\sqrt{n}/\varepsilon^2)$. Our work proves the lower bound, which matches (up to poly-logarithmic factors) the uniformity testing upper bound for general distributions (Canonne, Chen, Kamath, Levi, Waingarten~\cite{CCKLW21}). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Property Testing of Joint Distributions using Conditional SamplesACM Transactions on Computation Theory, 2018
- On Monotonicity Testing and Boolean Isoperimetric-type TheoremsSIAM Journal on Computing, 2018
- On the Power of Conditional Samples in Distribution TestingSIAM Journal on Computing, 2016
- An $o(n)$ Monotonicity Tester for Boolean Functions over the HypercubeSIAM Journal on Computing, 2016
- On Testing Expansion in Bounded-Degree Graphs2011
- Testing Symmetric Properties of DistributionsSIAM Journal on Computing, 2011
- Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements ProblemSIAM Journal on Computing, 2009
- Testing monotone high‐dimensional distributionsRandom Structures & Algorithms, 2008
- Isoperimetry, logarithmic sobolev inequalities on the discrete cube, and margulis' graph connectivity theoremGeometric and Functional Analysis, 1993