Local Computation of Maximal Independent Set

In this board talk, I will overview the Local Computation Algorithms (LCA) model of Rubinfeld et al. and Alon et al. for sublinear-time computations, and discuss how it addresses the above question. Then I will overview Rubinfeld's open question on LCAs for maximal independent set and maximal matching and some of the ideas that go into a very recent resolution of it. The paper's abstract is as follows.

We present a randomized Local Computation Algorithm (LCA) with query complexity $\poly(\Delta) \log n$ for the Maximal Independent Set (MIS) problem. That is, the algorithm determines whether each node is in the computed MIS or not using $\poly(\Delta) \log n$ queries to the adjacency lists of the graph, with high probability, and this can be done for different nodes simultaneously and independently. Here $\Delta$ and $n$ denote the maximum degree and the number of nodes. This algorithm resolves a key open problem in the study of local computations and sublinear algorithms, attributed to Rubinfeld.