6 Discussion In this paper we proposed new partition-based test statistics for both the indepen- dence problem and the two-sample problem. We proved that the statistics are con- sistent for general alternatives and demonstrated in simulations that the power ad- vantage of the tests based on finer partitions can be great. We further showed that the power of our regularized statistics is very close to that of the statistics based on the optimal partition size. We recommend the test using the minimum p -value statistic based on aggregation by summation, unless the alternative is suspected to be of very local nature. Specifically, in the K -sample problem if the difference between the distributions is on a very small range of the support, then the aggregation by maximization is preferred over aggregation by summation. The algorithms described in Section 3.1 for the test of independence based on reg- ularized scores for a range of m × m partitions can easily be generalized to include m$_{x}$ × m$_{y}$ partitions, where m$_{x}$ = m$_{y}$ , with the same complexity for the ADP statistic (for the DDP statistic m$_{x}$ = m$_{y}$ ). Considering unequal partition sizes for X and Y is expected to improve power when the (unknown) optimal partition has an m$_{x}$ value very different than the m$_{y}$ value. Moreover, when the (unknown) optimal partition has m$_{x}$ ≈ m$_{y}$ , the power loss from considering the minimum p -value over all m$_{x}$ × m$_{y}$ values instead of over all m × m values is expected to be small. The algorithms we suggested for the K -sample problem are O ( N $^{2}$) and therefore are feasible even for large N . For the test of independence, even though the complexity of our suggested algorithms is O ( N $^{4}$), for small N these algorithms can be quite efficient in the following quite common multiple testing setting in modern studies. If M hypotheses are simultaneously examined with the same sample size, then the computational complexity of using our distribution-free tests is O ( M × N $^{4}$) if null table 39