[Colloquium] Reminder: Show and Tell Series Talk (Today at 12:15)

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE 
SHOW AND TELL SERIES TALK
 
Speaker: Umut Acar
Speaker's homepage: http://www.tti-c.org//acar.html
 
Title: Self-Adjusting Computation
 
Time: Tuesday, January 18th, 12:15pm
Place: TTI-C conference room (1427 E. 60th St. - 2nd Floor) Lunch
provided
 
Abstract: 
I will talk about my thesis research.  I will present a summary of my 
previous work and talk about some applications.  The message of the 
talk will be this:  if a program or algorithm is "stable" for some set 
of changes to its input, then that algorithm can be made to adjust to 
such changes efficiently in a fully automatic manner.  The challenge is 
to devise a general purpose technique that can take advantage of the 
stability of an algorithm---ie, the fact that the executions of the 
algorithm on similar inputs are similar.  I will show that this is 
possible and consider a number of so-called dynamic problems and 
show that it is possible to devise stable algorithms for these 
problems.  I will show that the general purpose technique for making a 
program self-adjusting yields good asymptotic and practical efficiency 
even when compared to ad hoc solutions.
 
A more detailed abstract follows.
 
Self-adjusting computation refers to a model of computation where
programs automatically adjust to changes in their input or more
generally to changes in their environment.  For example, a
self-adjusting compiler can respond to changes in the program code by
recompiling the pieces of the code affected by the change.  As another
example, a self-adjusting convex-hull program can compute the convex
hull of a set of points as the points move continuously in the plane.
 
Techniques for enabling computations to respond to limited forms of
changes have been extensively studied in both the algorithms and in the
programming-languages community.  In the algorithms community, the focus
has been on obtaining fast algorithms that can respond to a prescribed
set of changes. These are called {\em dynamic algorithms}. Although this
approach yields efficient algorithms, dynamic algorithms are often
complex (even for simple problems), difficult to implement, and extend.
In the programming languages community, the focus has been on developing
general-purpose techniques to enable computations to respond to changes
automatically.  This is known as {\em incremental computation}.
Although incremental computation techniques can dramatically simplify
devising and implementing incremental/dynamic algorithms, the previously
proposed techniques fail to achieve adequate performance both in
asymptotic and practical terms.
 
This thesis proposes general-purpose language and algorithmic techniques
for self-adjusting computation.  On the one hand, I describe novel data
structure for tracking the dependences in a computation and a {\em
change-propagation} algorithm for updating a computation for a given
change.  I present a complexity analysis technique, called {\em trace
stability} for determining the performance of self-adjusting programs
based on change propagation. On the other hand, I describe language
facilities for writing self-adjusting programs in a type-safe manner and
prove that the change propagation algorithm is correct.  I present
efficient implementations for the proposed language facilities and
present some experimental results.
 
 
The results of this thesis enable devising, analyzing, and implementing
self-adjusting programs much like ordinary programs.  To demonstrate the
effectiveness of these techniques, I consider several algorithmic
problems including sorting, convex hulls, and dynamic trees and show
that self-adjusting computation yields efficient solutions to these
problems---as efficient as ad hoc solutions.
 
 
If you have questions, or would like to meet the speaker, please contact
Katherine at 4-1994 or kcumming at tti-c.org For information on future
TTI-C talks or events, please go to the TTI-C Events page:
http://www.tti-c.org/events.html
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20050118/b1b9c224/attachment.htm