High Performance Graph Algorithms and Data Structures

点击翻译按钮获取中文摘要

Computation on large scale data is closely connected with tools such as linear system solvers, convex optimization, and systems for storing dynamically changing networks. These tools are integrated in many high-level programming languages such as MATLAB, Python, and Julia, which are in turn widely used in machine learning, statistics, and scientific computing. The long term goal of this research program is to develop a new generation of algorithmic primitives suitable for inputs several order of magnitudes larger than what we currently process. Specifically, we hope to develop highly efficient and theoretically well-founded algorithms for processing graphs and sparse matrices in both static and dynamic settings. It builds upon recent breakthroughs in algorithms for fundamental graph problems, namely almost nearly-linear time solvers for graph structured linear systems, faster algorithms for network flows, and dynamic maintenance of higher connectivity values. The shorter term (5 year) objectives are: * Investigate and classify structured sparse linear systems, especially ones related to graphs, with the goal of refining and improving numerical primitives for manipulating them. * Develop almost linear time algorithms for solving wide ranges of graph optimization problems to high accuracy. * Better understand data structures for maintaining solutions of optimization problems on dynamically changing graphs. The proposed work revolves around two of the most widely used numerical primitives: iteration and elimination. Generalizing them to wide classes of computational problems will lead to a host of new algorithmic primitives suitable for the large-scale graph and sparse matrices. Such primitives are the silent workhorse of much of large-scale computation today, including the search engines that power the modern internet. Improvements on them have led to, and will continue to lead to, accelerated drug design, better social network analytics, more accurate recommendation of products to users, and more. This research program includes the supervision of both undergraduate and graduate students, the development of courses that connect numerical and combinatorial algorithms, as well as the organization of algorithmic problem solving outreach activities. Students involved will gain knowledge in the latest development of algorithms, develop independent research skills, and gain supervision/organization experiences through involvements in outreach activities. Such skills are highly sought after in both industry and academia: for example, the social media company Facebook has plans of hiring 35000 employees in its Bay Area facility, the web-based delivery company Amazon expanded by about 50% over the past year, the Computer Research Association reported that the size of CS programs tripled on average between 2006 and 2017, and major research universities hired over 70 faculties in theoretical computer science during the 2021-2022 cycle.