Search Results

We initiate the study of unate distributions over {±1}ⁿ - 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 Θ̃(n^{3/2}) samples are sufficient and necessary, in contrast to the Θ̃(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 Õ(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 Ω̃(n^{2/3}) complexity. In the same model, the complexity of monotonicity testing was recently shown to be Θ̃(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²) 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 {±}ⁿ.