[Colloquium] Reminder: today's talk by Umut Acar at 12:15 (at TTI-C)

[Margery Ishmael]

A JOINT TALK - DEPARTMENT OF COMPUTER SCIENCE
& TOYOTA TECHNOLOGICAL INSTITUTE IN CHICAGO

Date: Thursday, April 1, 2004
Time: 12:15 p.m.
Place: TTI-C, 1427 E. 60th Street (2nd floor)
----------------------------------------------------------------

Speaker:  UMUT ACAR, Carnegie Mellon University
Url: http://www-2.cs.cmu.edu/~umut/

Title: Self-Adjusting Computation

Abstract:

Many application domains require programs to react to a dynamically
changing environment: network links go down, roads get closed,
software gets modified, robots try to avoid moving objects etc.

In this talk, I introduce the concept of self-adjusting computation
which enables writing programs that adapt their output to changes in
their input.  Self-adjusting computation generalizes incremental
computation to support a much richer class of programs, including a
general method for obtaining dynamic versions of static algorithms
(i.e., dynamization).

Self-adjusting computation is based on a novel combination of
algorithmic and programming-language techniques.  Self-adjusting
programs maintain a record of the dynamic dependences that arise among
data values in a computation. This dependence information is then used
to adjust the result of the computation whenever any of the data
values change.  These mechanisms are placed under programmer control
through a type system that distinguishes changeable from stable values
and tracks all dependences to ensure correctness of the adaptive
results.  An analysis technique, called trace stability, enables the
programmer to determine the performance of self-adjusting programs.

Using these methods we provide self-adjusting versions of a number of
important algorithms, including Quicksort, MergeSort, Parallel Tree
Contraction, and several Convex-Hull algorithms.  The resulting
self-adjusting algorithms meet the bounds obtained for ad hoc dynamic
algorithms solving these problems.
----------------------------------------------------

Hosts: David McAllester & David MacQueen

**Refreshments will be provided**