Theory of Computing Seminar

Local Computation Algorithms (abbreviated LCAs) is a computational model aimed at problem instances with huge inputs and output. For graph problems, the input graph is accessed using probes, where a probe specifies the ID of a vertex and receives in reply the IDs of its neighbors.  Given a local query (e.g., ``is a certain vertex in the vertex cover of the input graph?''), an LCA should compute the corresponding local output (e.g., ``yes'' or ``no'') while making only a small number of probes. The requirement is that all local outputs form a single global solution (e.g., a legal vertex cover).

We study the possibilities and limitations of LCAs that are required to work on graphs that may have arbitrarily large degrees (even linear in $n$) but are limited to a number of probes that is significantly smaller than the minimal degree.

The talk is self-contained; I will not assume any knowledge of LCAs.

Joint work with Uriel Feige and Boaz Patt-Shamir.