The need to process increasingly large quantities of data has led to the emergence of graphs that are massive in scale. Processing such graphs poses unique algorithmic challenges because even linear time or linear working space can be prohibitively expensive. In this talk, I review several alternative models of computation that allow us to achieve sublinear time and/or space. I then focus on two examples of fundamental graph problems -- shortest paths and matching -- and present new frameworks for approaching these problems that are naturally well suited to massive graphs, and that lead to improved algorithms in many models of computation.
Aaron Bernstein is a researcher at Berlin University of Technology, focusing on algorithms and theoretical computer science. He received his PhD from Columbia University in 2016, advised by Cliff Stein.