Abstract: Finding strongly correlated pairs of observables is one of the basic tasks in data analysis and machine learning. Assuming we have N observables, there are N(N-1)/2 pairs of distinct observables, which gives rise to quadratic scalability in N if our approach is to explicitly compute all pairwise correlations.

In this talk, we look at algorithm designs that achieve subquadratic scalability in N to find pairs of observables that are strongly correlated compared with the majority of the pairs. Our plan is to start with an exposition of G. Valiant’s breakthrough design [FOCS’12,JACM’15] and then look at subsequent improved designs, including some of our own work.

Based on joint work with M. Karppa, J. Kohonen, and P. Ó Catháin, cf. https://arxiv.org/abs/1510.03895 (ACM TALG, to appear) and https://arxiv.org/abs/1606.05608 (ESA’16).

Speaker: Petteri Kaski

Affiliation: Professor of Computer Science, Aalto University

Place of Seminar: Aalto University