Speaker: Sushant Sachdeva, Yale University
Title: Fast Algorithms for Optimization and Learning on Graphs
From computing shortest routes, to analyzing social networks, computer science has tackled problems on graphs for over five decades. The dramatic increase in the sizes of graphs of interest has made the efficiency of algorithms increasingly important. Hence, we strive to design algorithms that run quickly, in time as close as possible to linear in the size of the input.
In this talk, I will demonstrate how tools from optimization, numerical linear algebra, and approximation theory can be used to design fast algorithms for three problems: 1) balanced graph partitioning, 2) regression on graphs, and 3) semi-supervised learning on graphs. In addition to excellent asymptotic bounds on running times, the resulting algorithms have superior performance in practice. I will conclude by discussing several challenges that lie ahead.
The talk will be self-contained and broadly accessible.
Sushant Sachdeva is a postdoctoral researcher working with Daniel Spielman at Yale University. He is interested in algorithms and their connections to optimization, machine learning, and statistics. His research focus is the design of fast algorithms for graph problems.
He spent Fall 2013 at the Simons Institute at Berkeley, supported by a Simons-Berkeley Research Fellowship. He received his PhD from Princeton University (2013), advised by Sanjeev Arora, and his BTech from IIT Bombay (2008) where he was awarded the President of India Gold Medal.