{"ID":5676055,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-05T00:53:01.582534842Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01573","arxiv_id":"2607.01573","title":"Testing Unate Distributions","abstract":"We initiate the study of *unate distributions* over $\\{\\pm1\\}^n$ -- a natural analogue of unate Boolean functions -- by considering two basic testing problems that parallel well-studied questions for monotone distributions: - Uniformity Testing of Unate Distributions: We show that $\\widetildeΘ(n^{3/2})$ samples are sufficient and necessary, in contrast to the $\\widetildeΘ(n)$ sample complexity of the analogous problem for monotone distributions (Rubinfeld and Servedio, STOC 2005; Adamaszek, Czumaj, and Sohler, SODA 2010). - Unateness Testing of Arbitrary Distributions: We give a tester that uses $\\widetilde{O}(n^{3/2})$ conditional samples in the subcube conditional model. On the other hand, every tester that draws conditional samples in a similar fashion, namely from $O(1)$-dimensional subcubes, must have an $\\widetildeΩ(n^{2/3})$ complexity. In the same model, the complexity of monotonicity testing was recently shown to be $\\widetildeΘ(n)$ (Chakrabarty et al., STOC 2025). Our algorithms for both problems significantly outperform the naive approach of reducing to the monotone case, which would incur $Ω(n^2)$ sample complexity. Our uniformity tester relies on a subroutine that \"weakly\" learns the hidden orientations of a unate distribution, together with a new correlation bound for these estimates. Both tools may be of independent interest in studying monotonicity and unateness over $\\{\\pm1\\}^n$.","short_abstract":"We initiate the study of *unate distributions* over $\\{\\pm1\\}^n$ -- a natural analogue of unate Boolean functions -- by considering two basic testing problems that parallel well-studied questions for monotone distributions: - Uniformity Testing of Unate Distributions: We show that $\\widetildeΘ(n^{3/2})$ samples are suf...","url_abs":"https://arxiv.org/abs/2607.01573","url_pdf":"https://arxiv.org/pdf/2607.01573v1","authors":"[\"Daeho Lee\",\"Shivam Nadimpalli\",\"Mingda Qiao\",\"Ronitt Rubinfeld\"]","published":"2026-07-02T01:07:04Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}