2. it is based on M$_{m}$,m ∈ { 2 ,...,m$_{max}$ } and lim$_{N}$$_{→∞}$ m$_{max}$/N = 0 or m$_{max}$ is finite. 1. it is based on S DDP m × m or S ADP m × $_{m}$, and lim$_{N}$$_{→∞}$ m$_{max}$/N 1 / 3 = 0 or m$_{max}$ is finite. 2. it is based on M DDP m × m and M ADP m × $_{m}$, and lim$_{N}$$_{→∞}$ m$_{max}$/ √ N = 0 or m$_{max}$ is finite. Theorem 2.6. Let the joint density of X and Y be h ( x,y ) , with marginal densities f ( x ) and g ( y ) . If there exists a point ( x$_{0}$,y$_{0}$ ) such that h ( x$_{0}$,y$_{0}$ ) is continuous and h ( x$_{0}$,y$_{0}$ ) = f ( x$_{0}$ ) g ( y$_{0}$ ) , i.e., there is local dependence at a continuous density point, then the permutation test based on min$_{m}$$_{∈{}$$_{2}$$_{,...,m}$$_{max}$$_{}}$ p$_{m}$ is consistent, if The proof of Theorem 2.6 follows in a straightforward way from the proofs of Theorem 2.2, see Appendix C for details. The proof of Theorem 2.5 follows similarly from the proof of Theorem 2.1, and it is omitted. For computing the above test statistics for a given N and partition size m , the compu- tational complexity of a naive implementation is exponential in m . We show in Section 3.1 more sophisticated algorithms for computing the aggregation by sum statistics for all m ∈ { 2 ,...,N } at once that have complexity O ( N $^{2}$) for the K -sample problem, and O ( N $^{4}$) for the independence problem. This is possible since instead of iterating over partitions, the algorithms iterate over cells. Moreover, the algorithms also enable calculating the regularized sum statistics of Section 2.1 in O ( N $^{2}$) and O ( N $^{4}$) for the K -sample and independence problems, respectively, since we just need to go over the list of m scores and for each score S$_{m}$ check its p-value in our pre-calculated null tables, which requires just an additional O ( N log( B )), where B is the null-table size. 20 3 Efficient algorithms