G. Valiant

2012

Citations

0

Influential Citations

0

Citations

Journal

Tiny Trans. Comput. Sci.

Abstract

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

copied to clipboard