Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On the Probe Complexity of Local Computation Algorithms
Speaker:Boaz Patt-Shamir
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:Boaz Patt-Shamir is a Professor of Computer Science in the School of Electrcal Engineering in Tel Aviv University since 1997, where he directs the laboratory for distributed algorithms. Prior to that, he was an assitant professor in Northeastern University in Boston. He received his BSc in Mathematics and Computer Science from Tel Aviv University, his MSc from Weizmann Institute, and his PhD from MIT.

His main research interest is network algorithms, including
self-stabilization, clock synchronization, routing, scheduling, and recommender systems. While on sabbatical in HP labs in Cambridge (Mass.), he helped develop an experimental corporate-intranet search engine based on his ideas for recommender systems.

He has served as the program committee chair for ACM PODC 2008 and SIROCCO 2010, and gave numerous invited talks in scientific conferences.

Event Type:AG1 Mittagsseminar (others' work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 12 March 2019
Duration:30 Minutes
Building:E1 4
In the Local Computation Algorithms (LCA) model, the algorithm is
asked to compute a part of the output by reading as little as possible
from the input. For example, an LCA for coloring a graph is given a
vertex name (as a "query"), and it should output the color assigned to
that vertex after inquiring about some part of the graph topology
using "probes"; all outputs must be consistent with the same coloring.
LCAs are useful when the input is huge, and the output as a whole is
not needed simultaneously. Most previous work on LCAs was limited to
bounded-degree graphs, which seems inevitable because probes are of
the form "what vertex is at the other end of edge i of vertex v?". In
this work we study LCAs for unbounded-degree graphs. In particular,
such LCAs are expected to probe the graph a number of times that is
significantly smaller than the maximum, average, or even minimum
degree. We show that there are problems that have very efficient LCAs
on any graph - specifically, we show that there is an LCA for the weak
coloring problem (where a coloring is legal if every vertex has a
neighbor with a different color) that uses log*n+O(1) probes to reply
to any query. As another way of dealing with large degrees, we propose
a more powerful type of probe which we call a *strong* probe: given a
vertex name, it returns a list of its neighbors. Lower bounds for
strong probes are stronger than ones in the edge probe model (which we
call *weak* probes). Our main result in this model is that roughly
Omega(sqrt(n)) strong probes are required to compute a maximal

Our findings include interesting separations between closely related
problems. For weak probes, we show that while weak 3-coloring can be
done with probe complexity log*n + O(1), weak 2-coloring has probe
complexity Omega((log n)/loglog n). For strong probes, our negative
result for *maximal* matching is complemented by an LCA for
(1-epsilon)-approximate *maximum* matching on regular graphs that uses
O(1) strong probes, for any constant epsilon>0.
Name(s):Christoph Lenzen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:This is joint work with Uri Feige and Shai Vardi.
Attachments, File(s):

Christoph Lenzen, 02/27/2019 05:52 PM
Last modified:
Uwe Brahm/MPII/DE, 03/12/2019 04:01 AM
  • Christoph Lenzen, 02/27/2019 05:52 PM -- Created document.