The Operations Research & Statistics seminar will be held on May 27,
Speaker: Shai Vardi from TAU
Title: Local computation algorithms
Time and place: 12:30 in Bloomfield-527
Local computation algorithms (LCAs) consider the scenario in which we
respond to queries (regarding a feasible solution) quickly and efficiently, but
we never need the entire solution at once. The replies to the queries need to
have the consistency property, namely, the responses to all possibly queries
combine to a feasible solution. For example, an LCA for matching in a graph
G, receives an edge-query for an edge e and replies “yes” if and only if e is part
of some specific matching M. The replies to all the possible queries define
M. In this talk, I will give a short introduction to LCAs, and show general
techniques for converting online algorithms and distributed algorithms to
The talk is based on joint works with Noga Alon, Yishay Mansour, Ronitt
Rubinfeld, Aviad Rubinstein and Ning Xie
You can watch the rest of the seminar plan at our web site
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>