1 Introduction Testing if two univariate random variables X and Y are independent of one another, given a random paired sample ( x$_{i}$, y$_{i}$ ) N i $_{=1}$, is a fundamental and extensively studied problem in statistics. Classical methods have focused on testing linear (Pearson’s cor- relation coefficient) or monotone (Spearman’s ρ , Kendall’s τ ) univariate dependence, and have little power to detect non-monotone relationships. Recently, there has been great interest in developing methods to capture complex dependencies between pairs of random variables. This interest follows from the recognition that in many mod- ern applications, dependencies of interest may not be of simple forms, and therefore the classical methods cannot capture them. Moreover, in modern applications, thou- sands of variables are measured simultaneously, thus making it impossible to view the scatter-plots of all the potential pairs of variables of interest. For example, Steuer et al. (2002) searched for pairs of genes that are co-dependent, among thousands of genes measured, using the estimated mutual information as a dependence measure. Reshef et al. (2011) searched for any type of relationship, not just linear or monotone, in large datasets from global health, gene expression, major-league baseball, and the human gut microbiota. They proposed a novel criterion which generated much inter- est but has also been criticised for lacking power by Simon and Tibshirani (2011) and Gorfine et al. (2011), and for other theoretical grounds by Kinney and Atwal (2014). A special important case is when X is categorical. In this case, the problem reduces to that of testing the equality of distributions, usually referred to as the K -sample problem (where K is the number of categories X can have). Jiang et al. (2014) searched for genes that are differentially expressed across two conditions (i.e., the 2-sample problem), using a novel test that has higher power over traditional methods such as Kolmogorov–Smirnov tests (Darling, 1957). 1