提出高维分布单调性测试的新方法，显著降低查询复杂度。
Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
- 用子立方体条件查询，结合方向等周不等式设计新算法。
- 单调性测试查询复杂度为近似 O(n/ε²)，下界匹配。
- 首次证明单调性对均匀性测试无帮助，仅可降对数因子。
研究高维分布于子立方体条件查询模型下的单调性测试问题。先前工作表明样本复杂度需指数级增长。本文证明子立方体查询复杂度为近似 Θ̃(n/ε²)，给出几乎紧的上下界。首次将函数单调性测试中的方向等周不等式应用于分布测试分析，并推广了 Khot、Minzer 与 Safra（2018）的不等式至实值函数。此外，研究了承诺单调分布的均匀性测试，证明其查询复杂度为近似 Θ̃(√n/ε²)，与一般分布的上界匹配（忽略对数因子），说明单调性在子立方体查询下对均匀性测试无实质帮助。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。