## SSS Abstracts |

This talk is in partial fulfillment of the speaking requirement.

I will describe two approaches to removing this drawback. The first is an interactive technique for intuitive editing of multi-body simulations. Our system allows the animator to select bodies at any time and simply drag them to desired locations. In response, the system interactively computes the required physical parameters and simulates the resulting motion. The second is a new off-line technique that constructs a physically realistic motion that matches the animator's rough sketch.

I will introduce a technique for creating novel, textually-enhanced thumbnails of web pages. These thumbnails combine the advantages of image thumbnails and text summaries to provide consistent performance on a variety of tasks.

In collaboration with others, I have performed a quantitative comparative study of textual and graphical summarization mechanisms applied to search engine results. Participants used three different types of summaries (enhanced thumbnails, plain thumbnails, and text summaries) to search web pages to find several different types of information. Participants took an average of 83 seconds to find the answer to a question. They were approximately 30 seconds faster with enhanced thumbnails than with text summaries, and 19 seconds faster with enhanced thumbnails than with plain thumbnails.

Based upon this data, I argue that graphical summaries of the documents - thumbnail images - can greatly increase the efficiency by which end-users process search engine result sets. For example, thumbnails allow users to classify a Web page's genre very rapidly. Most interestingly, our empirical results suggest that, if properly designed, textually-enhanced thumbnails deliver the efficiency benefits of both textual summaries and unenhanced thumbnails.

The work was performed at Xerox PARC during this previous summer.

In this talk, I present lower and upper bounds on the data locality of multithreaded programs where the threads are scheduled with the work-stealing algorithm. Work stealing is a randomized, simple-yet-efficient, widely-used algorithm for thread scheduling. In our analysis, we measure data locality by the number of cache misses; the lower the number of cache misses the better the locality. We consider various cache organizations and replacement policies such as direct mapped caches and LRU replacement policy.

For the lower bound, I show a computation that incurs only a constant number of cache misses when executed on a uniprocessor. At least $rac{1}{8}$ of all the instructions, however, causes a cache miss when the same computation is executed on a multiprocessor, even on $2$ processors. I generalize the computation to show an asymptotic lower bound. For the upper bound, I show that work stealing delivers good data locality for a large class of applications, nested-parallel applications. Based on the upper bound, I give strong execution time bounds for nested-parallel computations. Finally, I present experimental results showing that the data locality of work stealing can be further improved by associating affinities with threads. An affinity is a hint as to what processor should execute a thread. This idea is employed in most modern operating systems for process scheduling and is known as the affinity scheduling.

This is joint work with Guy Blelloch and Robert Blumofe.

This talk is in partial fulfillment of the speaking requirement.

Category theory is an abstract branch of mathematics that generalizes and relates ideas from algebra, geometry, topology, and logic. I will explain the main concepts and ideas of category theory from the logical and computational perspective.

Categories may be understood as collections of generalized sets and functions. I will motivate this view by analyzing how the usual concept of sets as static collections of elements can be an unsuitable mathematical framework for dealing with problems and concepts from everyday life and computer science. Concrete examples and category-theoretic solutions will be suggested.