Uncertainty Seminar

Local Computation Algorithms (abbreviated LCA) 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). In this talk, I will discuss the possibilities and limitations of LCAs that are required to work on graphs that may have arbitrarily large degrees (possibly linear in $n$) but are limited to a number of probes that is significantly smaller than the minimal degree.  I will present negative and positive results: I will show  probe complexity lower bounds for approximating the minimum vertex cover and for finding a maximal matching, and an algorithm for finding an approximate maximum matching on high-girth regular graphs that uses a constant number of probes.
Joint work with Uri Feige and Boaz Patt-Shamir.