Events

Fall 2016

# Uncertainty Seminar

Sep 29, 2016 11:00 am – 12:30 pm

Parent Program:

Speaker:

Location:

Calvin Lab Rm 116

## Local Computation Algorithms for High Degree Graphs

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.

Joint work with Uri Feige and Boaz Patt-Shamir.