The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science
                            Computer Science Seminar
                     Lecture Hall, Room 1, Ziskind Building
                          on Sunday, October 14, 2012
                                 15:00 - 16:00
                             Note the unusual time
                                   Eli Upfal
                                Brown University
                                 will speak on
                          Computing with Evolving Data
We formulate and study a new computational model for dynamic data. In this
model, the data changes gradually in time and the computation has access to
only a small part of the data in each step. The goal is to design algorithms
that output solutions to computational problems on the data at any given time.
As the data is constantly changing and the algorithm may not be aware of these
changes, it cannot be expected to always output the exact right solution; we
are interested in algorithms that guarantee good approximate solutions.
We study fundamental computation problems, including:  1. Sorting and
selection, where the true ordering of the elements changes in time and the
algorithm can only probe in each step the relative order of a few pairs; 2.
Connectivity and minimum spanning trees in graphs where edges' existence and
weight change over time and the algorithm can only track these changes by
probing a few vertex or edges per step; 3. Pagerank of a graph where edges
change over time and the algorithm tracks these changes by probing the
neighborhood of a few vertex per step;
This framework captures the inherent trade off between the complexity of
maintaining an up-to-date view of the data and the quality of results computed
with the available view.
(ITCS'12 and KDD12 - joint work with Aris Anagnostopoulos, Ravi Kumar, Mohammad
Mahdianb and Fabio Vandin.)
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <> 
Announcement from: Yaeli Malka   <>