But what if you want to say something like "This is a difficult optimization problem...in particular, there is no greedy algorithm that provides an optimal (or even good approximation) for this problem". Clearly, a precise definition is required if we want to defend such a statement.

In a paper co-authored with Morten Nielson and Charles Rackoff, we proposed a definition for greedy and greedy-like approximation algorithms, called priority algorithms. We did so in the context of classical scheduling problems . We also claimed that our definition could be extended (or be the basis for an extension) to other problem domains. More recently, Spyros Angelopoulos and I have applied the priority algorithm framework to the facility location and set cover problems. Russel Impagliazzo and Shaska Davis have also applied the framework to a number of traditional graph theoretic optimization problems.

Similar to the study of online algorithms, we are able to derive limitations on the (approximation) power of priority algorithms based only on the structure of the algorithm (allowing unbounded time complexity). In this talk, I will try to motivate the priority algorithm framework by discussing some well known greedy (or greedy-like) algorithms and the corresponding lower bounds we can prove within our framework. I will also mention some of the numerous open questions in this line of research.

This talk presents how security techniques can be integrated into group communication systems, a particular case of distributed messaging systems, while maintaining a reasonable level of performance. Many security services (data secrecy, data integrity, entity authentication, etc.) can be bootstrapped if members of the group share a common secret, which makes key management a critical building block. We propose an architecture for secure group communication, relying on a group key management protocol that is efficient, robust to process crashes and network partitions and merges, and protects confidentiality of the data even when long-term keys of the participants are compromised. We show how different group communication semantics can be supported in the proposed architecture, discuss the accompanying trust issues and present experimental results that offer insights into its scalability and practicality.

Brief Bio-sketch: Atul Prakash is a Professor in the Department of EECS at the University of Michigan. His research interests include security policy management, secure communication, security of downloaded code, and groupware systems. In the Antigone and Ismene projects, he has designed ways to support flexible security policies in group communication systems. In his groupware research, he has designed techniques to manage consistency in groupware systems and designed several toolkits, including DistEdit and Collaboratory Builder's Environment that have been used in large-scale collaboratory efforts such as the Upper Atmospheric Research Collaboratory project.

Execution performance of both commercial and scientific applications is critically determined by how efficiently the memory hierarchy can be utilized. Although modern computer systems provide many caches at different levels of the memory hierarchy, locality exploitation is not guaranteed. In this talk, I will give an overview of a large project on software and hardware support for effective locality-aware high performance computing. I will present three selective research topics: (1) cache optimization techniques at the application software level. (2) microarchitecture design for exploiting row buffer locality in DRAM, and (3) an efficient page replacement algorithm for buffer cache and its system software implementation. Through these case studies, I will discuss merits and limits of locality-aware techniques at different system levels.

BIO: Xiaodong Zhang is the Program Director of Advanced Computational Research at the National Science Foundation. His home institution is the College of William and Mary wherehe is a Professor of Computer Science. He has served on the editorial board of IEEE Transactions on Parallel and Distributed Systems, and is an associate editor of IEEE Micro. His research interests are in the area of high performance and distributed computing and systems, and computer architecture.

As part of our presentation, we discuss the construction of the roadmap, including how samples of the configuration space may be generated and how to connect the samples to form the roadmap. We then discuss the mapping from the workspace to the roadmap, explaining efficient techniques for its generation and representation. We continue with some robustness measures and how these may be used to enhance the robustness of the roadmap. We then present an extension of our method for mobile robots. Finally, we evaluate an implementation of our approach for serial-link manipulators with up to 20 joints.

BIOGRAPHY: Seth Hutchinson received his Ph. D. from Purdue University in West Lafayette, Indiana in 1988. He spent 1989 as a Visiting Assistant Professor of Electrical Engineering at Purdue University. In 1990 Dr. Hutchinson joined the faculty at the University of Illinois in Urbana-Champaign, where he is currently an Associate Professor in the Department of Electrical and Computer Engineering, the Coordinated Science Laboratory, and the Beckman Institute for Advanced Science and Technology.

Dr. Hutchinson is currently a senior editor of the {it IEEE Transactions on Robotics and Automation}. In 1996 he was a guest editor for a special section of the {it Transactions} devoted to the topic of visual servo control, and in 1994 he was co-chair of an IEEE Workshop on Visual Servoing. In 1996 and 1998 he co-authored papers that were finalists for the King-Sun Fu Memorial Best Transactions Paper Award. He was co-chair of IEEE Robotics and Automation Society Technical Committee on Computer and Robot Vision from 1992 to 1996, and has served on the program committees for more than thirty conferences related to robotics and computer vision. He has published more than 100 papers on the topics of robotics and computer vision.

My ultimate goal is to allow an untrained operator to walk into a city or building (e.g., a museum) and wave around some device that captures a digital model, which later can be used to provide many people the realistic visual experience of "walking" through the environment interactively. My approach is to take advantage of recent technology trends and to obtain a dense and automatic sampling of a large viewpoint space with omnidirectional images. This strategy replaces the difficult computer vision problems of 3D reconstruction and surface reflectance modeling with the easier problems of motorized cart navigation, data compression, and working set management.

I also provide a summary of related approaches and a research plan to capture and reconstruct large environments. This plan benefits from collaborative efforts in robotics (for building self-navigating high-resolution capture devices), computer vision (for developing image-reconstruction algorithms), and systems (for building and deploying large software systems over a network) and from developing applications to foment interactive tourism, to preserve historical sites, and to assist with simulation and training scenarios.

In this talk, I will describe three optimizations which substantially improve the performance and extend the power of the existing system. First, I give an optimized unification algorithm for logical frameworks which allows us to eliminate unnecessary occurs-checks. Second I present a novel execution model based on selective memoization and third I will discuss term indexing techniques to sustain performance in large-scale examples. As experimental results will demonstrate, these optimizations taken together constitute a significant step toward exploring the full potential of logical frameworks in real-world applications.

The Platform for Privacy Preferences (P3P), developed by the World Wide Web Consortium (W3C), provides a standard computer-readable (XML) format for privacy policies and a protocol that enables web browsers to read and process privacy policies automatically (http://www.w3.org/P3P/). P3P has been built into the Internet Explorer 6 and Netscape 7 web browsers and has been adopted by about a third of the top 100 web sites. We developed the AT&T Privacy Bird (http://privacybird.com) as an Internet Explorer add-on that can compare P3P policies against a user's privacy preferences and display a bird icon to indicate whether the user's preferences are met.

Developing interfaces for configuring P3P user agents with a user's privacy preferences is challenging due to the large number of potential choices to be made and the difficulties individuals have in describing privacy concerns in detail. As part of our Privacy Bird work, we developed a privacy preference specification interface. Our design was informed by privacy surveys and our previous experience with prototype P3P user agents. We conducted a user study to evaluate this interface and other aspects of Privacy Bird, and to gain a better understanding of how Privacy Bird is being used.

In this talk I will provide an overview of P3P, including some insights into the P3P development process. I will discuss the general problem of designing user interfaces for privacy and the specific design of the AT&T Privacy Bird. I will also present results from our Privacy Bird user study. Dr. Lorrie Faith Cranor is a principal technical staff member in the Secure Systems Research group at AT&T Labs-Research. She is chair of the P3P Specification Working Group at W3C and author of the book "Web Privacy with P3P" (O'Reilly 2002).

Refreshments will be served.