Massive systems and networks have become ubiquitous. While there is a remarkable amount of work on analyzing and designing algorithms for smaller systems, the vast majority of it simply does not scale: an algorithm that takes seconds to run on a system with thousands of nodes might take weeks on a system with billions. New ideas are required if we hope to have the same success with massive systems as we do with smaller ones.
The field of Local computation algorithms (LCAs), which I founded together with Ronitt Rubinfeld, Gil Tamir and Ning Xie, provides a rigorous framework for solving problems on huge systems. I will present one technique for designing LCAs: a reduction to online algorithms, and show how it can be used to design fast and robust distributed solvers for linear and convex programs. I will also describe how we can use insights from this technique to design approximate solvers for linear programs that have hitherto been unsolvable due to their size.
Shai Vardi is a Linde Postdoctoral Fellow at the Social and Information Sciences Laboratory at the California Institute of Technology, hosted by Adam Wierman. He spent the Fall semester of 2016-2017 at the Simons Institute for the Theory of Computation, and was previously a postdoc in the Weizmann Institute of Science, advised by Uri Feige. He received his MSc and PhD in Computer Science from Tel Aviv University, advised by Ronitt Rubinfeld and Yishay Mansour respectively. Shai received the Google European Fellowship for Game Theory for 2012-2015, and the iCORE Algorithms Postdoctoral Scholarship in 2015. He also has a diploma in jazz performance from the Rimon School of Jazz and Contemporary Music.