So the idea is pretty simple. Basically, they are asking, what is the mutual information between two variables? For those without a background in Inf. Theory: m

So the idea is pretty simple. Basically, they are asking, what is the mutual information between two variables? For those without a background in Inf. Theory: mutual information basically measures the amount of detail involved in knowing the two variables separately vs. knowing the combination of them. So if one variable can be predicted from the other perfectly, the mutual information is high, since knowing the two variables separately you would have to keep a lot of details, while knowing them together, you only need to know one. Information can be measured based on the discretization applied to the variables. They basically say if you look at all discretizations, then you can see if there is any way the two variables are related. Of course, they have to resort to an approximate algorithm. The idea is simple, and really, it is not new. I think a lot of non-parametric technicques try do the same. There software can be downloaded and I'd like to see its complexity and performance. I didn't find too much inf. on big O complexity or run times.