Guy Even
Local Computation Algorithms

Abstract: The model of Local Computation Algorithms (LCAs) was
invented by Rubinfeld et al. in 2011. The goal in designing an LCA is
to answer membership queries for a solution over graph. Computation of
answers to queries requires probing the graph, and the goal is to
design an LCA with the fewest number of probes per query.  We will
survey the main techniques that have been developed for designing LCAs
via the lens of computing approximate maximum matchings.  These tools
include: simulation of sequential algorithms via acyclic orientation,
random vertex ranking, deterministic vertex colorings, and simulation
of distributed algorithms.

Based on joint work with Moti Medina and Dana Ron.