Beating brute-force: Improved algorithms for finding correlations, and related problems.
Gregory Valiant · Tiny Trans. Comput. Sci. · 2012
Perhaps the most basic type of structure in a dataset is correlation. Computationally, how quickly can correlated variables be found? One can certainly brute-force search through all pairs of variables, and for each pair, the correlation can be approximated very eciently. But is there a sub-quadratic time algorithm for nding pairs of correlated variables? More generally, suppose one has a dataset where each data example has a label, given as some function of a small number of the variables. If we have n total variables, perhaps there is a small number, k = 2; 3; 4;:::, of relevant variables which can be used to predict the labels. Such a function is termed a k-junta. How quickly can one