CAREER: Scalable Algorithmic Primitives for Data Science

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This project aims to improve some of the most fundamental algorithms in computing: solving systems of linear equations, optimization on graphs, and maintaining dynamically changing networks. Tools for solving these problems are integral components of high-level programming languages such as MATLAB and Julia, and are frequently taught as basic programming constructs in courses on machine learning, statistics, and data science. Improved algorithms for these problems can provide faster, more robust, and easier-to-use algorithmic primitives, which would in turn enable computing on larger and more diverse data sets in areas such as data mining, image processing, scientific computing, and network science. The proposed works will actively involve graduate students, and their results will be incorporated into courses at both graduate and undergraduate levels. The project will also support the PI's long-time involvement with algorithmic problem-solving outreach activities, with a focus on making these activities more accessible to underrepresented groups, and institutionalizing the involvement of graduate students. The problems that this project proposes to study, linear system solvers and optimization on graphs, are some of the most well-studied problems in algorithm design. Previous work on these topics led to many widely-used algorithms and data structures. The main approach of this project is motivated by progress on combining numerical and combinatorial algorithmic primitives through the graph Laplacian matrix, known as the `Laplacian paradigm' for designing graph algorithms. Recent and ongoing work by the PI and collaborators led to the current best algorithms for many key problems involving graph Laplacians, and more importantly, significantly broadened the scope of problems addressed. An underlying theme in these results is that the most powerful tools work with intermediate algorithmic states, and the focus of this project is a more in-depth study of this phenomenon using ideas from data structures, which also construct and reuse intermediate algorithmic states. These directions of investigation will lead to new algorithmic constructs, give improved tools for computing on static and dynamic data, and enable new applications based on computations on graphs and matrices. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.