Lorenzo Orecchia, Institute Junior Fellow, Gives Jan 27, 2016 Meet Our Fellows Talk

3:00 PM – 4:00 PM on Wednesday, January 27, 2016
Hariri Institute for Computing, Room 180
Refreshments to follow

Efficient Algorithms and Intractable Problems Through the Lens of Convex Optimization

Lorenzo Orecchia
Junior Faculty Fellow, Hariri Institute for Computing
Assistant Professor, Computer Science Department

With an introduction by Mark Crovella, Chair of the Computer Science Department

Abstract: The algorithms we have learned (and now teach) in our Discrete Mathematics and Advanced Algorithms classes are based on a well-defined set of assumptions: efficient means polynomial time; the output must be an exact solution. Yet, the computational problems we face in everyday life often do not fit this bill. Huge datasets mean that our algorithms must run in linear or sublinear time. Approximate solutions are perfectly acceptable; the robustness of our solutions is more important than their exactness. Fortunately, there is another set of algorithmic techniques that is well suited to this new specification: continuous optimization techniques.  These algorithms are particularly appealing because they are inspired by the dynamics of the natural world around us. To draw an analogy, the computation of electrical currents running in a circuit requires the solution of a particular square system of equations, yet we do not believe that nature is performing Gaussian elimination. Instead, the electrons can be modeled as performing a local random walk over the circuit, whose aggregate frequencies converge to the solution of the system. Discretizing time, we can think of nature as running an algorithm that iteratively updates the potential, i.e., the density of electrons, at each node in the circuit, by performing small randomized updates.  Similar iterative methods lead to scalable, approximate solutions for a large number of convex optimization problems and are already a workhorse of numerical algorithms.

In this talk, Professor Orecchia will describe how techniques from continuous optimization are becoming an essential tool in the design and analysis of algorithms for discrete optimization problems, highlighting his work on nearly-linear-time algorithms for fundamental graph problems, such as maximum flow and graph partitioning. The presentation will briefly discuss where new ideas from convex optimization are taking the field of algorithms and how these developments should impact our work in the lab and classroom.

Bio: Professor Lorenzo Orecchia was selected as an Institute Junior Faculty Fellow in fall 2015. He is an assistant professor of Computer Science at Boston University, which he joined in 2015 from MIT, where he was a postdoctoral associate and an applied mathematics instructor. Lorenzo obtained his Ph.D. in computer science at the University of California, Berkeley. His research focuses on the theoretical study of algorithms, with the goal to design methods that are both mathematically sound and applicable in practice. Professor Orecchia’s research has produced algorithmic advances for foundational computational problems, both of combinatorial nature, such as graph clustering, and of continuous nature, such as the solution of systems of linear equations and of large resource-allocation linear programs. Professor Orecchia advocates a broad approach to the design of algorithm that incorporates techniques from discrete and continuous optimization and is able to model computational challenges arising in a variety of applications, including Machine Learning, Numerical Analysis and Combinatorial Optimization.