Principal Investigator Aleksander Madry
Project Website http://www.nsf.gov/awardsearch/showAward?AWD_ID=1553428&HistoricalAwards=false
Project Start Date January 2016
Project End Date December 2020
Graphs are at the heart of computer science and many other fields. They model various complex systems, such as the structure of web links, social networks, road systems, protein interactions, and the brain. Also, many elements of our everyday life, such as web search, driving directions, online advertising and parcel delivery, crucially rely upon graph algorithms. Despite this central role and extensive research on graphs, however, some of the most prominent questions in algorithmic graph theory remain unresolved. Additionally, in the era of big data, the graphs that we have to deal with are often massive - they have hundreds of billions of edges - which renders many classic graph algorithms completely infeasible.
The goal of this project is to address these challenges by augmenting our traditional graph-algorithmic techniques with methods borrowed from continuous optimization. In particular, the PI aims to forge a unified toolkit that is powerful enough to make progress on a variety of fundamental graph problems. An integral part of this effort will be to broadly disseminate the acquired insights. Dissemination will encompass undergraduate and graduate curriculum development, production of freely available lecture notes/survey, as well as training students, of all levels, to equip them with the skill set that is essential for tackling modern graph-algorithmic challenges.
From a more technical point of view, the main focus of this project will be to combine the classic combinatorial approaches of algorithmic graph theory with core continuous-optimization primitives, such as gradient descent methods and interior-point methods, to break longstanding running time barriers for a variety of fundamental flow and matching questions. Additionally, the PI expects that this work will shed new light on one of the central challenges of mathematical programming: the convergence behavior of interior-point methods, and will also lead to novel extensions of that optimization framework.