Testing Unate Distributions
For researchers in distribution testing and property testing, this work establishes the first results for unate distributions, showing they are harder than monotone distributions but easier than general distributions.
The paper initiates the study of unate distributions over {±1}^n, providing sample complexity bounds for uniformity testing (Θ̃(n^{3/2})) and unateness testing (Θ̃(n^{3/2}) conditional samples, with an Ω̃(n^{2/3}) lower bound for O(1)-dimensional subcube queries). These results significantly improve over the naive Ω(n^2) reduction to monotone distributions.
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$.