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
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 <firstname.lastname@example.org>
Announcement from: Yaeli Malka <email@example.com>