Brown CS News

Black, Herlihy, Krishnamurthi, Lysyanskaya, Tamassia and van Dam Awarded Substantial Funding from NSF

The National Science Foundation has recently awarded to Brown University funding in the expected overall amount of $2.2 million for the research projects of six faculty members: Michael Black, Maurice Herlihy, Shriram Krishnamurthi, Anna Lysyanskaya, Roberto Tamassia and Andy van Dam.

Michael Black Michael’s project, entitled “Detailed Human Shape and Pose from Images,” aims to develop methods to perfect the estimation of human pose in video sequences. Over a three-year period, funding in the expected amount of $370,000 will be provided for this research.

Michael’s project will go beyond previous work on estimating human pose from video sequences to also estimate human body shape. The majority of images and video sequences contain humans and understanding human action in video is a core problem in computer vision. Currently, marker-based human pose estimation is used in areas such as gait analysis, special effects, game development, human factors and sports training. According to Michael, current methods for estimating human pose might best be described as “brittle.” His work aims to improve human pose by using a much more realistic model of the human body and by exploiting a rich set of image cues over time. Over the course of this research project, methods will be developed to robustly recover body shape even when it is obscured by clothing, exploit illumination and surface geometry to more accurately estimate human shape and pose and recover body pose and shape in “natural” video sequences with uncalibrated and moving cameras.

Michael believes that this work on robust human tracking will have applications in home entertainment, elder care, autonomous vehicles and animal movement analysis. By also recovering body shape, the proposed methods will enable additional applications in video forensics, surveillance, avatar creation and special effects.

Maurice Herlihy Maurice has been awarded a grant in the expected amount of $250,000 in support of his project “A Unified Open-Source Transactional-Memory Infrastructure,” which aims at developing an open-source infrastructure to support transactional memory, a synchronization mechanism for multicore architectures.

As general-purpose computing moves into the age of pervasive parallelism, programmability becomes the key hurdle limiting the effective use of available computing resources. Transactional memory promises to simplify parallel programming for application programmers. However, research in transactional memory is being seriously hampered by the lack of a reusable open source infrastructure. The project will develop the key pieces necessary to overcome this situation:

A transactional memory (TM) library built out of highly decomposed pieces will provide reusable and replaceable parts suitable for investigating tradeoffs in software TM implementations. Standardized interfaces will allow libraries conforming to the interfaces to be used in a variety of environments. TM-aware run-time analysis tools, particularly profilers and debuggers, will provide the necessary tool support for TM implementors and application programmers to understand and improve the performance of software using transactions. Interesting benchmarks, in a variety of high-level languages, will move forward our understanding of TM performance characteristics.

Shriram Krishnamurthi

Shriram and his collaborators Daniel Dougherty and Kathi Fisler at Worcester Polytechnic Institute, have received funding in the expected amount of $400,000 (of which $200,000 awarded to Brown) for their project entitled, “Power to the People: Tools for Explaining Access-Control Consequences.”

This research aims to create a more inclusive, trustworthy and effective cyberspace for all users, especially those who do not wish to become familiar with the innards applications. As computer-assisted social networking and related phenomena gain traction, the number of such users is bound to increase, even as their relative technical sophistication falls. These end-users have been turned into authors of access-control policies without realizing it. Everywhere from Google to Facebook, these policies are usually hidden behind simple user interfaces, but ultimately the users are responsible for setting and then taking responsibility for the consequences of these policies.

Because applications are a mystery to end-users, it becomes difficult for users to predict the consequences of an action. Users see only their view of the world, but their access-control decisions affect the views of others. End-users need tools to determine the effect of their decisions, with special emphasis on the effect of policy changes. This project focuses on developing user-friendly means to browse and investigate the details of these effects and changes. The underlying techniques are firmly grounded in theory, resulting in formal accuracy guarantees rather than approximate answers. The tools themselves summarize information in ways that account for the cognitive expectations and biases of users. Some end-users are too eager to embrace new technologies without fully appreciating their consequences, while others are too tentative due to their concern about (sometimes imaginary) problems they might create. The tools from this project will help the former become more cautious, and the latter more confident.

Anna Lysyanskaya

Anna’s project, “Crypto Algorithms for an Integrated Approach to Conditional, Revocable and Traceable Anonymity” has been awarded funding, in the expected amount of $300,000, to investigate techniques that allow one to develop and enforce anonymity contracts between individuals and organizations that spell out what can become known about the individual user and under what circumstances.

As records of individuals' activities become increasingly computerized and linked, privacy becomes an ever more challenging problem. It is especially challenging when legitimate security needs require the ability to link different transactions and even obtain details about the individuals involved. The focus of this project is on cryptographic technologies that achieve a compromise: transaction records should be anonymous until special circumstances (such as wrong-doing on the part of a particular individual, or an emergency that requires special measures) arise. One wants to specify these circumstances before a transaction takes place, so an individual can choose not to participate in a transaction that does not provide him or her with sufficient privacy guarantees.

The project considers several trade-offs between anonymity and accountability. Conditional anonymity/conditional disclosure means that an individual user is anonymous until her activities violate a certain condition, at which point some piece of information about her becomes known. Revocable anonymity means that a user is anonymous to all but a special anonymity-revoking trustee that only becomes involved in case of emergency. Traceable anonymity means that, under special circumstances, it is possible to quickly trace all of a particular user's transactions; this can be a form of conditional anonymity where the circumstances are due to the user's misbehavior or revocable anonymity where a trustee decides when to run the trace algorithm.

Roberto Tamassia

Roberto and his collaborators Michael T. Goodrich and David Eppstein at the University of California-Irvine have received funding in the expected amount of $600,000 (of which $200,000 awarded to Brown) for their project entitled “Algorithms for Graphs on Surfaces.” This research explores the fundamental questions on geometric and spatial aspects of graphs and networks, with applications to road networks, sensor networks, computer networks, and social networks.

The investigators will develop methods for constructing effective geometric layouts of networks on surfaces and in three-dimensional space and for analyzing properties of networks by exploiting their geometric structure. The focus of the project is the design and analysis of algorithms for graphs on surfaces in the following three thrust areas: (1) algorithms for embedding graphs on surfaces, including methods for greedy embeddings of graphs to facilitate geometric routing, algorithms for manifold triangulation for a set of points sampled from an embedded surface, and techniques for drawing trees in the plane; (2) algorithms for graphs embedded on surfaces, including the study of connections between partial cubes and integer lattices, the development of algorithms for graphs embedded in non-Euclidean spaces, and the design of methods for solving graph problems on quadrilateral meshes; (3) applications of algorithms for graphs on surfaces, including applications of geometric graphs to computer security and algorithms for road networks.

Andy van Dam

Andy recently received funding in the expected amount of $300,000 for his research project, “End-User Retrofitting of Applications by Recognizing Text and UI Components.”

Despite the enormous effort that goes into application design, end users invariably encounter workflow scenarios that are poorly supported by even the most developed, commercial-quality applications. Lack of support for end-user extension increases the burden on application developers to exhaustively anticipate the needs of all end users and then to commit enough resources to address their needs, which often includes re-implementing solutions already found in other applications. This project develops the feasibility of externally retrofitting, without altering, running applications with new interfaces and functionality made possible by using a combination of application-independent pixel-level recognition techniques and more specialized techniques for inspecting data structures exposed by the window system or application. Users will be able to make annotations to those running applications, including hand-drawn ink, typed text, diagrams, interactive widgets, or even links to other application user interface components. Rather than waiting, possibly years, for even simple revisions to fix workflow inefficiencies, users will be empowered to make limited modifications to applications almost as easily as marking up a document.

Next entry

Previous entry