Technion
 
The Operations Research & Statistics seminar will be held on May 27,
2013
 
____________________________________________________________________________
 
Speaker: Shai Vardi from TAU
 
Title: Local computation algorithms
 
Time and place: 12:30 in Bloomfield-527
 
Abstract:
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
LCAs.
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   <techm@math.technion.ac.il> 
Announcement from:  <tomerk@.technion.ac.il>