Research Areas Summary

to 25th Anniversary home

Research Areas TOC

Agents and Ecommerce Educational Technology Research Robotics and Computer Vision
Artificial Intelligence Internet Computing Scientific Visualization and Scientific Computing
Combinatorial Algorithms Mobile and Ubiquitous Computing Security and Cryptography
Combinatorial Optimization Nanotechnology Software Engineering and Programming Environments
Computational Biology Neuroinformatics and Brain Science Theory of Computation
Computational Geometry and Graph Drawing Operating Systems and Distributed Systems Theory of Networking, Concurrency, and Distributed Computing
Computational Linguistics Parallel Computation User Interfaces and Virtual Reality
Computer Graphics Programming Languages Verification and Reliable Systems
Database Management Systems Randomized Algorithms and Probabilistic Analysis

CS Department Researchers

Agents and Ecommerce

(Tom Dean, Amy Greenwald, Thomas Hofmann, Eli Upfal, Pascal Van Hentenryck)

 

The Agents and Ecommerce group at Brown is designing and implementing systems that automate decision-theoretic and game-theoretic reasoning. One of our key objectives is to develop faithful representations of user preferences, thereby facilitating human-computer interaction. Given a single user’s preferences, we apply statistical techniques to designing agent-based information retrieval systems that automatically annotate, classify, filter, retrieve, and deliver web content. Given multiple users’ preferences, we are implementing agents that learn to reason strategically in ecommerce settings, such as Internet auctions and other dynamic pricing games. Another objective of the group is to investigate commodity trading and portfolio optimization applications, which give rise to hard stochastic combinatorial optimization problems.

 

 

Artificial Intelligence

(Michael Black, Eugene Charniak , Tom Dean , Amy Greenwald, Thomas Hofmann , Mark Johnson, Leslie Pack Kaelbling Pascal Van Hentenryck )

  Artificial intelligence is concerned with elucidating the principles behind intelligent behavior by creating artifacts (computer programs) that embody such principles. AI researchers at Brown tend to see probability and statistics as the primary mathematics in which these principles are to be expressed, while recognizing that various cognitive areas have quite different specifics. We also have a bias towards seeing the specific problems in which we are interested (e.g., vision, language, temporal reasoning, economic behavior, brain implants) as special instances of machine learning—that is, we believe that in a surprisingly wide variety of cases, the best way to get a program to solve some problem is to have it learn to solve the problem. Thus AI researchers at Brown share not just a common set of problems but a substantial set of tools with which to approach them.

 

 

Combinatorial Algorithms

(Philip Klein, Franco Preparata, John Savage, Roberto Tamassia, Eli Upfal)

  Combinatorial algorithms treat computations on finite, discrete mathematical structures. Topics include searching, sorting, and enumeration, data structures, graph algorithms, external-memory algorithms, combinatorial optimization, approximation algorithms for NP-hard problems, online algorithms, and algorithm engineering.

 

 

Combinatorial Optimization

(Amy Greenwald, Philip Klein, Pascal Van Hentenryck)

  Combinatorial optimization involves finding the best (e.g. cheapest, most valuable, smallest, biggest) among a huge but finite set of candidates. Examples include job-shop scheduling and the traveling salesman problem. Research at Brown focuses on three areas:
  • Solution methods for traditional optimization problems, including methods for finding exact solutions (e.g. constraint and integer programming, dynamic programming), approximation algorithms that are guaranteed to find solutions nearly as good as the best, and heuristic methods that find good solutions for most but not all possible instances.
  • Stochastic and on-line optimization problems in which the data are uncertain and/or not known a priori.
  • Modeling tools that streamline the development of solution methods.

 

 

Computational Biology

( Ioannis Kontoyiannis , Franco Preparata , Eli Upfal , Pascal Van Hentenryck)

  Computational biology is a vigorous emerging discipline at the interface of computer science and life science and is at the core of bioinformatics, which is concerned with the acquisition, analysis, and storage of biological information. Computational biology is the development of algorithms and computer programs central to this effort, with special emphasis on nucleic acid and protein sequence applications. Subjects of active research include DNA mapping, sequence alignment, data mining in biological databases, phylogeny, spatial structures, and functional genomics and proteomics.

 

 

Computational Geometry and Graph Drawing

( Franco Preparata , Roberto Tamassia )

  Theoretical research in this area addresses data structures and algorithms for fundamental geometric problems, robust geometric primitives, computational metrology and tolerancing, computational topology, geometric graph theory and graph-drawing algorithms. Experimental work includes software libraries for 2D and 3D geometric computing and Internet-based tools for graph visualization.

 

 

Computational Linguistics

( Eugene Charniak , Thomas Hofmann , Mark Johnson , Ioannis Kontoyiannis )

  Computational linguistics is the study of language through the use of computers. At Brown we tend to view the field as a branch of artificial intelligence (as opposed to a quite different view that might be held by, say, lexicographers). We also share the statistical and machine-learning biases mentioned above in the description of AI at Brown. More specifically, we are interested in the use of statistical learning techniques in the study of parsing (from simple context-free parsing to more complex unification-based grammars), speech (parsing it, recognizing and handling disfluencies, etc.), machine translation, document and answer retrieval, lexical acquisition, and language modeling (specifically its uses in speech recognition and machine translation).

 

 

Computer Graphics

( John Hughes , David Laidlaw , Juergen Schulze, Andy van Dam )

  The graphics group works on several areas—modeling, animation, interaction, and fundamental algorithms. In modeling, we’re interested in direct modeling rather than modeling from captured or scanned objects, model representation, and nonphotorealistic rendering. In animation, we’re interested in human figure animation, both with and without the use of captured human motion data. Our emphasis is on physical plausibility and the relationship between animation and robotics. In interaction, we’ve worked on interfaces for modeling, the measurement of interaction and tracking technologies in our Cave and other virtual environments, and novel 2D and 3D interaction techniques. We also study mathematical foundations for graphics algorithms, especially provably correct algorithms for modern hardware.

 

 

Database Management Systems

( Ugur Cetintemel , David Durand, Dina Goldin , Stan Zdonik )

  We have been leaders in object-oriented database systems and advanced query languages and query processing. We have a strong interest in data management for networked systems, including the intelligent use of resources for broadcast and dissemination-based systems. We focus on the emerging area of data-stream management systems (DSMS) with an emphasis on real-time processing, quality of service maintenance, and approximate answers. Our work also includes content-based data access in wireless and ad hoc networks.

 

 

Educational Technology Research

( Roger Blumberg , Shriram Krishnamurthi , Roberto Tamassia , Andy van Dam )

  Since its inception, the department has had a strong track record of research in interactive educational technology and tools. Current projects include the Exploratories project to create interactive illustrations, embedded in hypermedia frameworks; JERPA, a system for managing and distributing programming assignments and their associated support material; and ReMarkable Texts, an innovative note-taking system designed for TabletPCs. In addition, we are ongoing participants in the design of DrScheme, one of the leading teaching-motivated and student-friendly programming environments. The department also offers a seminar in educational software in which students create software based on the needs of local teachers.The seminar - CS92 - has produced dozens of programs for K-12, higher education and educational institutions such as the Providence Children's Museum.

 

 

Internet Computing

( Ugur Cetintemel , John Jannotti , Shriram Krishnamurthi , Steve Reiss , Stan Zdonik )

  In Internet computing we work on such topics as data prefetching, proxy cache management, and resource discovery. We are also working on the use of profiles in performing automatic data organization and in support of adaptive content-management networks. We are looking at the use of XML as a basis for intelligent document management, for data retrieval, and as a format for data interchange. We are also developing languages and tools to support the development, evolution, and understanding of large-scale Internet-based programs, including the semantics and verification of Web services.

 

 

Mobile and Ubiquitous Computing

( Ugur Cetintemel , Tom Doeppner , John Jannotti , Don Stanford , Stan Zdonik )

  Recent years have witnessed a dramatic trend towards ubiquitous computing, whereby very large numbers of casually accessible, mobile or embedded computing devices are connected to an increasingly ubiquitous networking infrastructure. In this context, our research explores a host of data and resource management challenges in newly emerging networked systems, such as sensor networks, mobile ad hoc networks, and Internet-scale information systems. Specific projects include profile-based data management; broadcast disks; data recharging; mobile computers (with ad hoc networking) as note-taking, annotation, and collaboration tools; decentralized replication for mobile and weakly connected environments; and adaptive data dissemination in wireless sensor networks.

 

 

Nanotechnology

( John Savage )

  Nanocomputing, the use of nanometer-scale technologies for computation, presents important new algorithmic challenges. Self-assembly will replace traditional photolithography as a means to place circuit designs on chips. As a result, nanochips will be highly regular and faulty. Among the many new challenges are a) the discovery of efficient algorithms for the structural programming of nanochips containing hundreds of millions of programmable sites, b) development of architectures and algorithms to make the best use of the I/O limitations that arise due to the disparity in wire sizes at the nano- and microlevels, and c) the design of new algorithms for the efficient use of highly structured, faulty nanoscale structures.

 

 

Neuroinformatics and Brain Science

( Michael Black , Tom Dean , Thomas Hofmann , Ioannis Kontoyiannis , David Laidlaw )

  As part of a larger interdisciplinary brain sciences initiative at Brown, neuroinformatics combines neuroscience and informatics in order to advance our understanding of how the brain works. Methods from various branches of computer science are utilized to visualize, model, and simulate neural processes. Areas of particular interests include human-computer interfaces, computational and statistical models of sensory processing and motor control, adaptivity and learning in the brain, and the use of computer graphics to enhance brain-imaging technology.

 

 

Operating Systems and Distributed Systems

( Ugur Cetintemel , Tom Doeppner , Maurice Herlihy , John Jannotti , Steve Reiss , Don Stanford )

  Brown has a long history of research in operating systems and distributed systems, ranging from early work in RPC protocols in the early ’70s to early work in multithreaded programming in the ’80s and a fair number of research activities today that focus on a number of different areas. Within distributed systems we are working on decentralized data replication and caching and adaptive distributed resource management. We are interested in technologies that apply data-management techniques to distributed environments, such as distributed caching, data broadcast, and automated data freshening. We also address data management in sensor networks and in data dissemination systems. We are pursuing techniques for understanding the behavior of distributed systems through analysis and visualization, as well as developing environments to support the construction and maintenance of distributed systems. At the more fundamental level we are working in the foundations and practice of wait-free and lock-free synchronization algorithms, in the context of both shared-memory multiprocessors and distributed systems. Finally, in operating systems we continue our work in multithreaded programming with particular emphasis on performance of shared-memory parallel systems.

 

 

Parallel Computation

( Maurice Herlihy , Franco Preparata , Steve Reiss , John Savage , Eli Upfal )

  Research in parallel computation deals with models of execution in which sets of independent operations can be carried out concurrently. Therefore it is concerned with formalization of models of parallelism, elucidation of problem parallelism, design of parallel algorithms, space-time tradeoffs, computing system layout, and investigation of the limits to parallelizability.

 

 

Programming Languages

(David Durand, Dina Goldin , Philip Klein , Shriram Krishnamurthi , Steve Reiss , Pascal Van Hentenryck )

  Programming language research at Brown covers the design, implementation, and analysis of programming languages. We focus on three main areas. First, we study and construct different notions of modularity, with a strong nod to the principles derived from software engineering concerns. Our work covers functional, object-oriented, and newer programming-language paradigms. Second, we build highly declarative programming languages centered around constraints, with special emphasis on combinatorial and numerical constraints. Finally, we are interested in the principles and problems underlying popular programming methodologies such as scripting.

 

 

Randomized Algorithms and Probabilistic Analysis

( Michael Black , Philip Klein , Ioannis Kontoyiannis , Anna Lysyanskaya , Eli Upfal , Pascal Van Hentenryck )

  We study applications of probability theory to the design and analysis of algorithms. Randomness comes up in two aspects of the study of algorithms: randomized algorithms and probabilistic analysis of algorithms. In randomized algorithms, we are particularly interested in algorithms for communication and distributed applications, as well as online combinatorial problems. In probabilistic analysis, our work focuses on the long-term steady-state performance of dynamic processes.

 

 

Robotics and Computer Vision

( Michael Black , Tom Dean , Thomas Hofmann )

  Problems in robotics and computer vision reside at the boundary between the physical world and computational machines and hence present interesting challenges for the computer scientist. In particular, our computational models of the physical world are, by necessity, incomplete, which means that when we observe or act upon the world we do so with inaccurate, uncertain, and ambiguous information. Research on vision and robotics at Brown focuses on this problem of sensing, acting, and reasoning in an uncertain world. Our research includes robot path planning, map learning, learning to navigate, generalizing example human motions to robotic and animated actors, video motion analysis, tracking, event recognition, human motion understanding, applications of vision in computer graphics, and the neural control of robotic devices. Our work spans many disciplines and involves collaborations with researchers in Engineering, Neuroscience, Cognitive and Linguistic Sciences, and Applied Mathematics. Our facilities include a Vicon motion-capture system, high-speed multi-camera video capture equipment, mobile sensor platforms, and robot arms.

 

 

Scientific Visualization and Scientific Computing

( Cullen Jackson, David Laidlaw , John Savage , Andy van Dam , David Zeltzer )

  Driven by scientific applications, research in this area centers around toolsmithing, creating, building, and evaluating computational and visualization tools for science. Problem areas include visualization of time-varying 3D vector- and tensor-valued data, information visualization, image processing, classification and segmentation, biological modeling, load balancing in a distributed environment, and distributed finite element mesh refinement.To attack these problems, we develop new user interface environments and metaphors, look for inspiration from art to create new visual representations, and develop new numerical approaches to model complicated scientific data and physical phenomena computationally and visually. Active collaborations with archaeologists, fluids researchers, neurosurgeons, developmental biologists, medical imaging researchers, orthopaedic surgeons, bioengineers, perceptual psychologists, and evolutionary biologists help to motivate, guide, and evaluate the research. The many application areas help ensure that the computational and visualization tools are broadly useful. Research in this area is coupled with other areas in the department, in particular Computer Graphics, Neuroinformatics and Brain Science, and User Interfaces and Virtual Reality.

 

 

Security and Cryptography

( Tom Doeppner , Philip Klein , Anna Lysyanskaya , Roberto Tamassia )

  Our goal is to protect communication and computation from malicious attacks. We work on efficient and provably secure solutions to basic problems such as encryption, digital signatures and their revocation, anonymity and privacy, and the group key distribution (multicast). We also develop practical tools for such tasks as combating denial-of-service attacks (via IP-traceback), certificate revocation, XML signatures and the authentication of Web services. On a more theoretical level, we are interested in general methodologies for constructing secure protocols, in multi-party computation and in cryptographic assumptions and primitives.

 

 

Software Engineering and Programming Environments

( Shriram Krishnamurthi , Steve Reiss , Don Stanford )

  Software engineering is the study of effective ways to design, implement, validate and maintain extremely large software systems. Our research stresses the construction of software tools, especially in the context of programming environments. Our work currently focuses on the consistent evolution of software, the bridge between the structure and behavior of software systems, and on combining tools in an integrated environment. We are also part of the multi-university PLT Scheme project, which produces the DrScheme programming environment.

 

 

Theory of Computation

( Maurice Herlihy , Philip Klein , Shriram Krishnamurthi , Anna Lysyanskaya , Franco Preparata , John Savage , Roberto Tamassia , Eli Upfal )

  Researchers in theoretical computer science at Brown develop serial, parallel, and distributed models of computation, establish fundamental limits on computation, identify problems that are computationally feasible and infeasible, not only classify problems by their use of computational resources, such as space, time, number of I/O operations, and chip area, but also examine tradeoffs between resources, study the expressive power of programming languages, explore the nature of proof, develop the foundations for reliable and secure communications, and develop verifiable methods for the specification of tasks.

 

 

Theory of Networking, Concurrency, and Distributed Computing

( Dina Goldin , Maurice Herlihy , Shriram Krishnamurthi , Anna Lysyanskaya , Eli Upfal , Peter Wegner )

  Researchers in theoretical computer science at Brown develop serial, parallel, and distributed models of computation, establish fundamental limits on computation, identify problems that are computationally feasible and infeasible, classify problems by their use of computational resources, such as space, time, number of I/O operations, and chip area, and also examine tradeoffs between resources, study the expressive power of programming languages, explore the nature of proof, develop the foundations for reliable and secure communications, and develop verifiable methods for the specification of tasks.

 

 

User Interfaces and Virtual Reality

( Michael Black , John Hughes , Cullen Jackson, David Laidlaw , Juergen Schulze , Andy van Dam , David Zeltzer )

  Brown's user interface research spans a broad range of form factors, including traditional desktop interfaces, large-format displays, new interaction devices, stereo displays, and fully immersive virtual-reality environments. We develop new interaction metaphors, evaluate their effectiveness, compare the different types of environments to develop an understanding of their strengths and weaknesses, and, in collaboration with the Rhode Island School of Design, study how the design process can complement the development of user interfaces. Our evaluations are often driven by scientific visualization and 3D modeling applications, both of which lend a 3D focus. Facilities include several small-scale “fishtank” virtual-reality setups and the only Cave virtual environment in the northeast. This research area is closely coupled with Computer Graphics and with Scientific Visualization and Scientific Computing. In collaboration with scientists in the Brain Sciences Program, we are building a new generation of direct brain-machine interfaces using implanted electrode arrays to control computer displays and robotic devices.

 

 

Verification and Reliable Systems

( Shriram Krishnamurthi , Pascal Van Hentenryck )

  Our main focus is on the modular verification of systems. We place particular emphasis on software systems, addressing the problems peculiar to them and exploiting the advantages they confer. Our verification work is strongly informed by our expertise in programming languages and software engineering. A second focus is the design and implementation of reliable and validated numerical algorithms, including nonlinear and differential equations, using interval reasoning.

CS Department Researchers

Michael Black, Associate Professor
     Research Groups:
         Artificial Intelligence
         Neuroinformatics and Brain Science
         Randomized Algorithms and Probabilistic Analysis
         Robotics and Computer Vision
         User Interfaces and Virtual Reality
Roger Blumberg, Visiting Assistant Professor
     Research Groups:
         Educational Technology Research
Ugur Cetintemel, Assistant Professor
     Research Groups:
         Database Management Systems
         Internet Computing
         Mobile and Ubiquitous Computing
         Operating Systems and Distributed Systems
Eugene Charniak, Professor
     Research Groups:
         Artificial Intelligence
         Computational Linguistics
Tom Dean, Professor
     Research Groups:
         Agents and Ecommerce
         Artificial Intelligence
         Neuroinformatics and Brain Science
         Robotics and Computer Vision
Tom Doeppner, Associate Professor (Research)
     Research Groups:
         Mobile and Ubiquitous Computing
         Operating Systems and Distributed Systems
         Security and Cryptography
David Durand, Adjunct Associate Professor (Research)
     Research Groups:
         Database Management Systems
         Programming Languages
Dina Goldin, Adjunct Assistant Professor
     Research Groups:
         Database Management Systems
         Programming Languages
         Theory of Networking, Concurrency, and Distributed Computing
Amy Greenwald, Assistant Professor
     Research Groups:
         Agents and Ecommerce
         Artificial Intelligence
         Combinatorial Optimization
Maurice Herlihy, Professor
     Research Groups:
         Operating Systems and Distributed Systems
         Parallel Computation
         Theory of Computation
         Theory of Networking, Concurrency, and Distributed Computing
Thomas Hofmann, Assistant Professor
     Research Groups:
         Agents and Ecommerce
         Artificial Intelligence
         Computational Linguistics
         Neuroinformatics and Brain Science
         Robotics and Computer Vision
John F. Hughes, Associate Professor
     Research Groups:
         Computer Graphics
         User Interfaces and Virtual Reality
Cullen Jackson, Post-Doc
     Research Groups:
         Scientific Visualization and Scientific Computing
         User Interfaces and Virtual Reality
John Jannotti, Assistant Professor
     Research Groups:
         Internet Computing
         Mobile and Ubiquitous Computing
         Operating Systems and Distributed Systems
Mark Johnson, Professor of Cognitive & Linguistic Sciences
     Research Groups:
         Artificial Intelligence
         Computational Linguistics
Leslie Pack Kaelbling, Adjunct Professor of Computer Science
     Research Groups:
         Artificial Intelligence
Philip Klein, Professor
     Research Groups:
         Combinatorial Algorithms
         Combinatorial Optimization
         Programming Languages
         Randomized Algorithms and Probabilistic Analysis
         Security and Cryptography
         Theory of Computation
Ioannis Kontoyiannis, Assistant Professor of Applied Mathematics
     Research Groups:
         Computational Biology
         Computational Linguistics
         Neuroinformatics and Brain Science
         Randomized Algorithms and Probabilistic Analysis
Shriram Krishnamurthi, Assistant Professor
     Research Groups:
         Educational Technology Research
         Internet Computing
         Programming Languages
         Software Engineering and Programming Environments
         Theory of Computation
         Theory of Networking, Concurrency, and Distributed Computing
         Verification and Reliable Systems
David Laidlaw, Associate Professor
         Computer Graphics
         Neuroinformatics and Brain Science
         Scientific Visualization and Scientific Computing
         User Interfaces and Virtual Reality
Anna Lysyanskaya, Assistant Professor
     Research Groups:
         Randomized Algorithms and Probabilistic Analysis
         Security and Cryptography
         Theory of Computation
         Theory of Networking, Concurrency, and Distributed Computing
Franco P. Preparata, Professor
     Research Groups:
         Combinatorial Algorithms
         Computational Biology
         Computational Geometry and Graph Drawing
         Parallel Computation
         Theory of Computation
Steve Reiss, Professor
     Research Groups:
         Internet Computing
         Operating Systems and Distributed Systems
         Parallel Computation
         Programming Languages
         Software Engineering and Programming Environments
John Savage, Professor
     Research Groups:
         Combinatorial Algorithms
         Nanotechnology
         Parallel Computation
         Scientific Visualization and Scientific Computing
         Theory of Computation
Juergen Schulze, Post-Doc
     Research Groups:
         Computer Graphics
Donald Stanford, Adjunct Professor (Research)
     Research Groups:
         Mobile and Ubiquitous Computing
         Operating Systems and Distributed Systems
         Software Engineering and Programming Environments
Roberto Tamassia, Professor
     Research Groups:
         Combinatorial Algorithms
         Computational Geometry and Graph Drawing
         Educational Technology Research
         Security and Cryptography
         Theory of Computation
Eli Upfal, Professor and Department Chair
     Research Groups:
         Agents and Ecommerce
         Combinatorial Algorithms
         Computational Biology
         Parallel Computation
         Randomized Algorithms and Probabilistic Analysis
         Theory of Computation
         Theory of Networking, Concurrency, and Distributed Computing
Andy van Dam, Professor
         Computer Graphics
         Educational Technology Research
         Scientific Visualization and Scientific Computing
         User Interfaces and Virtual Reality
Pascal Van Hentenryck, Professor
     Research Groups:
         Agents and Ecommerce
         Artificial Intelligence
         Combinatorial Optimization
         Computational Biology
         Programming Languages
         Randomized Algorithms and Probabilistic Analysis
         Verification and Reliable Systems
Eileen Louise Vote, Post-Doc
         Scientific Visualization and Scientific Computing
Peter Wegner, Professor Emeritus
     Research Groups:
         Theory of Networking, Concurrency, and Distributed Computing
Stan Zdonik, Professor
     Research Groups:
         Database Management Systems
         Internet Computing
         Mobile and Ubiquitous Computing
David Zeltzer, Adjunct Associate Professor
     Research Groups:
         Scientific Visualization and Scientific Computing
         User Interfaces and Virtual Reality

For comments and questions concerning this Web site
please send mail to the 25th Anniversary webmaster