Spring 2003
February 20, 2003
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).
February 24, 2003
April 3, 2003
The logical framework Twelf provides an experimental platform to specify, implement and execute formal systems. One of its applications is in proof-carrying code and proof-carrying authentication, where it is successfully used to specify and verify formal guarantees about the run-time behavior of programs. These real-world applications have exposed some critical bottlenecks: execution of many logical specifications is severely hampered and some are not executable at all, thereby limiting its application in practice.
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.
April 10, 2003
Computer simulation of real-world environments is one of the grand challenges of computer graphics. Applications for this technology include remote education, virtual heritage, specialist training, electronic commerce, and entertainment. Unfortunately, current computer graphics techniques fall far short of providing solutions for this challenge. In this presentation, I present a new approach to capturing and rendering large real-world environments, including several successful demonstrations and future research plans.
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.
April 11, 2003
We present a new method for generating collision-free paths for robots operating in changing environments. Our approach is closely related to recent probabilistic roadmap approaches. These planners use preprocessing and query stages, and are aimed at planning many times in the same environment. In contrast, our preprocessing stage creates a representation of the configuration space that can be easily modified in real time to account for changes in the environment. As with previous approaches, we begin by constructing a graph that represents a roadmap in the configuration space, but we do not construct this graph for a specific workspace. Instead, we construct the graph for an obstacle-free workspace, and encode the mapping from workspace cells to nodes and arcs in the graph. When the environment changes, this mapping is used to make the appropriate modifications to the graph, and plans can be generated by searching the modified graph.
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.
Speaker 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.
April 17, 2003
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.
Speaker Biography: 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.
May 1, 2003
Secure group communication technology can be an enabling platform for building many kinds of distributed applications. However, our experience indicates that applications often have varying requirements in terms of security. Furthermore, many applications require a different notion of a group than that in traditional group communication applications where groups are fairly static and messages are generally sent to all members of the group. Instead, a large class of applications requires more selective addressing, where a message needs to be securely delivered to a changing subset of the group. This talk presents results from our investigation of these issues. We discuss Ismene, a language for supporting flexible security policies in multi-party communication. We also present results from our work on key management in content-based publish-subscribe systems where secure selective addressing in a group is required.
Speaker Biography: 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.
May 8, 2003
This talk is about a domain-specific language for robot programming embedded in the functional language Haskell. Our language, Functional Robotics (Frob), is built upon the hybrid systems framework Functional Reactive Programming (FRP). I will first present the key ideas and abstractions of FRP and then show how it can be instantiated for robot programming. A robot program has a reactive part which defines the robot behavior and a planning part for composing complex tasks from simpler ones. Both dimensions are addressed in Frob by the help of a rich set of combinators and abstractions. Because of the declarative style of Haskell modular, resuable, and intuitive programs can be developed enabling rapid prototyping. I will present a visual tracking based robot navigation system developed in Frob which shows different domains like vision and user interfaces can be integrated into our language by using the same framework. Finally, I will talk about the relationship between FRP programs and formal hybrid system specifications and show how an FRP program can be transformed into a corresponding hybrid systems specification. Such a tranformation makes the formal analysis methods developed for hybrid systems available for Frob and other FRP-based programs.
May 9, 2003
Distributed applications increasingly rely on messaging systems to provide secure, uninterrupted service within acceptable throughput and latency parameters. This is difficult to guarantee in a complex network environment that is susceptible to a multitude of human or electronic threats, especially as network attacks have become more sophisticated and harder to contain. Security is a critical component of the survivability of such distributed messaging systems that operate in a dynamic network environment and communicate over insecure networks such as the Internet.
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.
May 16, 2003
Most Computer Science department teach an undergraduate course call something like Introduction to Algorithms or the Fundamentals of Algorithmics or the Design and Analysis of Algorithms (to plagiarize the titles of some well known texts). Some of these courses and texts often organize the material in terms of “Algorithmic Paradigms”, such as greedy algorithms, dynamic programming, local search, etc. We seem to be able to intuitively describe what we have in mind when we discuss these classes of algorithms but rarely (if ever) do we( or any of the standard texts) attempt to define precisely what we mean by greedy, or dynamic programming. I have often said “you’ll know one when you see one”.
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.
June 3, 2003
Joint work with Avrim Blum and Shuchi Chawla (CMU) And David Karger and Maria Minkoff (MIT) And Terran Lane (University of New Mexico)
Consider a robot which delivers various packages. The robot needs to visit a series of locations, and the quality of the path selected is determined by the timeliness of the deliveries. We can assume that the robot recieves a reward for each package delivered, where the reward is determined by the package identity and the delivery time. Our goal is to find a path which maximizes the total reward.
In this talk, we consider two different functions relating reward to time. In the Orienteering problem, the rewards are fixed until a specified time, at which point all rewards drop to zero. This is the problem of maximizing the number of destinations visited before a specific deadline. In the Discounting problem, the reward decays exponentially with time. This model is frequently considered in the realm of Markov decision processes. For each of these two functions, we describe the first constant approximation algorithms.
June 4, 2003
In this talk I present two recent results in the area of ad-hoc routing. In the first part I discuss the only local (thus practical in a mobile ad-hoc network environment) dominating set construction with non-trivial worst-case guarantees. Having a small dominating set is an important stepping stone for reactive ad-hoc routing algorithms such as AODV or DSR. In the second part of the talk I present GOAFR, a geometric (a.k.a. geographic, location- or position-based) routing algorithm. Simulations show that GOAFR is the most efficient geometric routing algorithm; in addition, GOAFR is also the only algorithm that is asymptotically optimal in the worst case. It is widely believed that understanding ad-hoc routing will lead to a deeper understanding of routing in general.
The first part is joint work with Fabian Kuhn; the second part with Aaron Zollinger and Fabian Kuhn.
Speaker Biography: Roger Wattenhofer received his doctorate in computer science in 1998 from ETH Zurich, Switzerland. From 1999 to 2001 he was in the USA, first at Brown University in Providence, RI, then at Microsoft Research in Redmond, WA. Currently he is an assistant professor at ETH Zurich. Roger Wattenhofer’s research interests include a variety of algorithmic aspects in networking and distributed computing; in particular, peer-to-peer computing and ad-hoc networks.
July 24, 2003
At Duke University we use interactive visualizations to aid the learning process in a wide-range of courses including CS0, CS1, CS2 and Mathematical Foundations. We present two software tools we have developed, JAWAA and JFLAP, and show how we use them in teaching computer science concepts. JAWAA is a scripting language for creating animations easily over the web. JAWAA includes primitives, easy creation of data structures and operations on these structures, and an editor for easy creation of complex objects. We have used JAWAA in all four courses mentioned above. JFLAP is a comprehensive software tool for experimenting with concepts in a formal languages and automata theory course that is currently used around the world in over 40 countries. With JFLAP one can explore the concepts of automata, grammars, parsing, L-systems, and the conversion of one representation of a language to another. For example, one can enter in a regular expression, convert it to an NFA, then a DFA, then a minimum state DFA and then back to a regular expression. We will describe how JFLAP and JAWAA aid in visualizing and interacting with computer science concepts.