Abstract
I will describe recent work on Local Computation Algorithms on average case inputs. In the Local Computation Algorithm (LCA) model, we are given probe access to a huge graph, and asked to provide fast consistent answers to queries about and underlying combinatorial structure on the graph.
For instance, an LCA for the k-spanner problem gives access to a sparse subgraph H ⊆ G that preserves distances up to a factor of k. We build simple LCAs for this problem assuming the input graph is drawn from the well-studied random graph models. Our spanners achieve size and stretch tradeoffs that are impossible to achieve for general graphs, while having dramatically lower query complexity than worst-case LCAs.
Our second result investigates the intersection of LCAs with Local Access Generators. Local Access Generators provide efficient query access to a random object, for instance an Erdos-Renyi random graph. We explore the natural problem of generating a random graph together with a combinatorial structure on it. We show that this combination can be easier to solve than focusing on each problem by itself, by building a fast, simple algorithm that provides access to an Erdos-Renyi random graph together with a maximal independent set.
In contrast, I will recall a few of the more quirky non-average stories of working with Dana over the years.
Joint work with Amartya Shankha Biswas, Ruidi Cao, Cassandra Marcussen and Ted Pyne.