Aaron Sidford joins Stanford’s Management Science & Engineering department, launching new winter class CS 269G / MS&E 313: “Almost Linear Time Graph Algorithms.” Sidford sat down with The Daily to discuss his research interests in optimization and algorithms and his outlook on joining the Stanford community.

The Stanford Daily (TSD): Can you introduce yourself?

Aaron Sidford (AS): I am a theoretical computer scientist by training. I went to graduate school at MIT working on graph algorithms. I began my PhD with an interest in more classical combinatorial optimization problems. As I started working in the area, I became interested in areas like continuous optimization and numerical analysis that were making substantial theoretical progress on even classic combinatorial problems. As a result, my interests broadened rapidly during my graduate studies, and now most of the research I do is somewhere between continuous optimization and combinatorial optimization. I also dabble in problems that I think are motivated by large data sets using a mixture of machine learning and statistics as well.

TSD: How did you become interested in your research area originally?

AS: At the time I started grad school, there was this cool breakthrough result by my advisor and a number of other researchers. The result involved viewing a graph as a network of resistors and using fast algorithms to simulate electric current to solve maximum flow a little faster. The previous best algorithms were roughly on the order of number of edges to the 3/2 and it had been, and still is, a big theoretical question as to what degree a large graph has structure that we exploit to achieve faster runtimes. My adviser and other researchers at the time decreased the 3/2 exponent to roughly 4/3. I’m glossing over a bit here, but the results were very exciting and groundbreaking. The result used an intriguing mix of combinatorial and continuous optimization techniques that got me hooked.

TSD: What are your key research interests right now?

AS: Usually the research I do involves trying to achieve faster algorithms for extracting information from large datasets. In the combinatorial world, this means questions like getting even faster algorithms for problems like maximum flow which is still a big open problem. There are a lot of tools that were developed in the last decade to get faster graph algorithms in a variety of different settings that I am still actively working on improving and expanding. In fact, the class I am teaching [this] quarter is going to discuss these. In the continuous world, this means obtaining provably faster iterative methods and better running times for numerous problems like linear system solving, linear programming, and even flavors of non-convex optimization.

TSD: Can you talk a little more about the course that you will be teaching?

AS: So the class will be about graph algorithms that operate in approximately linear time. Imagine having a very large graph and you want to extract some property out of it. You want to solve some problem on the graph ideally in almost linear time. Over the last decade there has been an increasing suite of techniques that, on the one hand, decomposes large graphs to find certain clusterings and substructures of the graph and, on the other hand, uses that structure to then solve a much larger class of problems in near linear time. The course will focus on exploring this suite of techniques.

TSD: How have you liked your time at Stanford so far?

AS: If you look at the community here, between CS, MS&E, Stats, Math and ICME, and the professors in those departments, there is  really a group of people interested in hard problems in algorithm design and optimization. I think that a lot of great things happen for the research when you have that sort of critical mass of students and researchers and people generally excited. For me,  community has been a driving force in deciding to come to Stanford, and so far it has been very fun. I have been working with some people in CS, some people in Stats, some people in MS&E, and it’s been great. Coming to Stanford has been another research uptick, and I am excited to see where it will go. I am also looking forward to advising more as well.

TSD: What do you enjoy doing outside of your academic interests?

AS: I run and play Ultimate. I also recently started biking. Unfortunately, I have not had a chance to go on many of the hikes around here yet, but they are on the to-do list. I have ran the Dish many times. So far there has been a lot to get used to, and the recent few months have been really busy, especially my field in particular. I look forward to exploring the area more.

This transcript has been lightly edited and condensed.

Contact Nancy Xu at xnancy ‘at’ stanford.edu.