提出可复现分布检测新框架，解决多个经典问题的样本复杂度下界。
Replicable Distribution Testing
- 构建可复现性约束下的分布检测算法，实现离散分布近似与独立性测试。
- 建立新下界证明方法，给出均匀性与近似性检测的近最优样本复杂度。
- 为算法可复现性研究提供新范式，适合关注理论严谨性的研究人员。
我们首次在算法可复现性框架下系统研究分布检测问题。给定来自一组概率分布的独立样本，目标是刻画检测其自然属性的样本复杂度。算法方面，提出了新的可复现算法用于离散分布的相近性与独立性检测；下界方面，发展了一种新的可复现检测样本复杂度下界证明方法，具有更广适用性。作为应用，我们建立了可复现均匀性检测和相近性检测的近最优样本复杂度下界，解决了先前工作中的一个开放问题。
原文摘要 · Abstract (English)
We initiate a systematic investigation of distribution testing in the framework of algorithmic replicability. Specifically, given independent samples from a collection of probability distributions, the goal is to characterize the sample complexity of replicably testing natural properties of the underlying distributions. On the algorithmic front, we develop new replicable algorithms for testing closeness and independence of discrete distributions. On the lower bound front, we develop a new methodology for proving sample complexity lower bounds for replicable testing that may be of broader interest. As an application of our technique, we establish near-optimal sample complexity lower bounds for replicable uniformity testing -- answering an open question from prior work -- and closeness testing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。