New Techniques for Local Computation Algorithms
March 2, 2016
Given an input $x$ and a search problem $F$, local computation algorithms (LCAs) implement access to specified locations of $y$ in a legal output $y \in F(x)$, using polylogarithmic time and space. Parnas and Ron (2007) and Mansour et al. (2012) showed how to convert certain distributed and online algorithms to LCAs, respectively. We expand on those lines of work and develop new techniques for designing LCAs and bounding their space and time complexity.
Joint work with Omer Reingold.
BIO:
Shai Vardi is a postdoctoral fellow of Computer Science and Applied Mathematics at the Weizmann Institute of Science. He recently completed his PhD in Computer Science at Tel Aviv University under the supervision of Yishay Mansour. Shai works on local computation algorithms, online algorithms, and algorithmic game theory.