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 Abstract: 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 <techm@math.technion.ac.il> Announcement from: Yaeli Malka <yaeli.malka@weizmann.ac.il>