We initiate the study of unate distributions over $\{\pm1\}^n$, a natural analogue of unate Boolean functions, focusing on two fundamental testing problems that parallel well-studied questions for monotone distributions:
-
Uniformity Testing of Monotone Distributions: We demonstrate that $\widetilde{\Theta}(n^{3/2})$ samples are both sufficient and necessary, contrasting with the $\widetilde{\Theta}(n)$ sample complexity for the analogous problem in monotone distributions (Rubinfeld and Servedio, STOC 2005; Adamaszek, Czumaj, and Sohler, SODA 2010).
-
Unateness Testing of Arbitrary Distributions: We present a tester that utilizes $\widetilde{O}(n^{3/2})$ conditional samples in the subcube conditional model. Conversely, any tester that draws conditional samples similarly from $O(1)$-dimensional subcubes must have a complexity of $\widetilde{\Omega}(n^{2/3})$. In the same model, the complexity of monotonicity testing has recently been shown to be $\widetilde{\Theta}(n)$ (Chakrabarty et al., STOC 2025).
Our algorithms for both problems significantly outperform the naive approach of reducing to the monotone case, which incurs an $\Omega(n^2)$ sample complexity. Our uniformity tester relies on a subroutine that "weakly" learns the hidden orientations of a unate distribution, along with a new correlation bound for these estimates. Both tools may be of independent interest in studying monotonicity and unateness over $\{\pm1\}^n$.
Blogger's Review: This paper reveals profound connections between testing unate distributions and monotonicity, particularly highlighting significant differences in sample complexity, which merits further exploration for practical applications.