- General
- Research
- Education
- Admissions
Research Labs
- Theory and Algorithms
- ISTS: Institute for Security Technology Studies
- The Neukom Institute for Computational Science
- Center for Mobile Computing
- Robotics Lab
- Sensor Networks Group
- Image Science Group
- PKI Lab
- CRAWDAD Wireless Data Archive
Research Projects
Multimodal Protein Structure
How is oxygen carried around in blood, how are invaders recognized by cells, and how is food digested? Answers to these and other questions about the molecular machinery of the cell (and potentially how to modify it) center on analysis of three-dimensional protein structures. We are embedding computation as a core component of structural studies, planning experiments to maximize the information gained, interpreting the results so as to characterize remaining uncertainty, and iterating. For example, reasoning by analogy to other proteins, we can predict possible models for a new protein (see figure). Then we can analyze their differences (e.g., distances between landmarks, overall envelopes, surface vs. core locations) and optimize experimental probes for these differences, employing "multimodal" sets of probes to overcome the noise and sparsity characteristics of any individual experimental type.
Family-Based Protein Design
Family reunions can be very interesting. Proteins have relatives (across organisms and even within the same organism) that are similar, but also different in significant ways. For example, shown in the figure are one serine protease (blue; function is to chop up other proteins) and one of its inhibitors (red; function is to block the chopping mechanism, as shown). Different proteases recognize different places to chop, while different inhibitors have different degrees of inhibition for different proteases. We are developing techniques to learn from nature's exploration of these families -- generalizing common features of observed family members and characterizing their differences, and relating these to experimental observations about their functions. This enables us to optimize our own new variants with desired functions (e.g., particularly strong and protease-specific inhibitors).
Robotic Origami Folding
Thin materials like sheet metal, paper, and cardboard are lightweight, inexpensive, and can be stored and shipped in bulk. Folding allows the construction of semi-rigid 3-D structures, including fast-food containers, paper bags, and file cabinets. Folding can also allow a single large surface or chain to be stored in a small volume; motivating examples include car airbags, space-telescope mirrors, and proteins. Finally, folding allows reconfiguration, without the need for disassembly and reassembly.
We have built the first origami-folding robot (left), capable of folding a paper hat, paper airplane, and paper cup. We have also analyzed more complicated folding techniques; work with Erik and Martin Demaine questions whether ordinary paper shopping bags can be mathematically folded.
Exact Optimal Trajectories for Robots
Robot control algorithms, like computer algorithms, allocate resources to accomplish tasks; resources include time, energy, degrees of freedom, steps of computation, and precision. A fundamental problem is to determine the minimum resources required -- the physical complexity of of the task. The optimal trajectories provide insight into the capabilities of a mechanism, independent of compromises introduced by particular planning or control techniques.
The exact optimal trajectories were previously known for two vehicles: the Dubins car, and the Reeds-Shepp car. We have discovered the optimal trajectories for a third vehicle; the common differential-drive (wheelchair-like) robot, and work on two more vehicles is nearing completion.
Wireless Sensor Networks
The next big thing in networking, and arguably one of the most fascinating and coolest technologies to hit the scene since the Internet, is wireless sensor networks. These tiny, low-cost wireless devices embed on-board sensing, are fully programmable, and can spontaneously form large sensor webs with thousands of distributed sensor devices. The potential of this fast-emerging field seems huge.
The Sensor Networks Group is focused on people-centric sensing through the development of new networking protocols to make mobile sensor networks robust, scale-free, and flexible to program - in essence, to make these new networks useable for the future deployment of emerging people-centric sensing applications.
Approximate Nearest Neighbour Searching
Nearest neighbour searching is one of those basic and fascinating theoretical problems in computer science that has a host of applications in problems from very diverse fields. The problem is widely believed to be intractable in high dimensions, but good approximation algorithms were discovered in the late 1990s.
Our research considers the approximate nearest neighbour search (ANNS) problem on the d-dimensional Hamming cube. Building on techniques of information complexity and communication complexity from an earlier research project of ours, we prove the first unrestricted lower bound for this problem. We also improve previous algorithms for this problem, ending up with matching upper and lower bounds on the number of randomised queries required to solve ANNS.
Shown in the figure is a schematic of the reduction bridging communication complexity and ANNS, a key step in our proof.
FG
High-performance computing with disk-resident data? Although that might seem like an oxymoron, we are developing a software environment, FG, to enable it.
FG is for asynchronous programs that run on clusters and fit into a pipeline framework. Each pipeline stage corresponds to a function that operates on a buffer. Multiple buffers traverse the pipeline and correspond to blocks in the memory hiearchy. Stages run asynchronously (via threads) in order to make it easy to overlap their operations (computation, communication, and I/O).
Using FG, we have developed programs that can sort well in excess of 100 gigbytes of data. (Image, left, shows Tom's whiteboard covered with deep thoughts about pipelines.)
Brain Engineering
Our brains are the most complex objects known to man. We cannot yet explain how our brains recognize, learn, plan, or use language. Yet these tasks are so natural for us they seem effortless. Through extensive interdisciplinary collaborations, the Brain Engineering Laboratory combines research from neuroscience, computer science, and cognitive science to advance our understanding of how brains operate. We aim to understand brain circuits sufficiently well to be able to imitate their function. We have extensive publications in this interdisciplinary field, as well as a range of applications that have been developed for medical and commercial uses.
Price and Allocation Algorithms for Markets and Networks
We seek a better understanding of the behavior of decentralized systems such as markets and traffic networks, through the study of effective resource allocation and price determination for these systems.
Markets:
Why might markets tend toward and remain near equilibrium prices? We assume that a collection of more or less simple procedures underlie the actions of participants in the actual economy. We aim to explain why price changes in market economies might work effectively by showing simple distributed algorithms that cause prices to converge quickly toward equilibrium values. The goal of this work is to better understand price adjustment mechanisms that operate independently on each price yet achieve a coordinated outcome.Network Traffic:
Individual network users may have an adverse impact on network performance, by acting in their own interests instead of the aggregate interest. We study equilibria of routing games to understand possible outcomes of selfish routing decisions; and we anayze methods such as taxation, rerouting, network design and policy to try and control this.Digital Image Forensics
We no longer live in a world where seeing (or hearing) is believing. The technology that allows for digital media to be manipulated and distorted is developing at break-neck speeds. And at the same time, our understanding of the technological, ethical, and legal implications is lagging behind.
We are, therefore, developing mathematical and computational algorithms to detect tampering in digital media. To do so, we quantify statistical correlations that result from specific forms of digital tampering, and devise detection schemes to reveal these correlations.
Reconstructing Ancient Egyptian Tombs
It is ironic that the Ancient Egyptian tombs, once sealed, were not intended to be seen by outsiders. Yet the highly valued and often reproduced tomb decorations have had a profound influence on art and have contributed significantly to our understanding of the Ancient Egyptian culture.
We describe how recent advances in computational and digital technology can add a new perspective to these marvels of antiquity. Of particular interest to us has been the development of a technique for the digital reconstruction of tombs, allowing for the creation of undistorted panoramic views of tomb interiors that are simply unattainable with traditional imaging methods.
Security through measurement for wireless LANs
Prof. David Kotz, Prof. Andrew Campbell
With the rise of Voice over wireless LAN (VoWLAN), any complete WiFi security solution must address denial of service attacks, such as kicking off other clients, consuming excessive bandwidth, or spoofing access points, to the detriment of legitimate clients. Even an authorized client may be able to sufficiently disrupt service quality to make the network ineffective for legitimate clients.
We take a three-point, MAP (Measure, Analyze, Protect) approach to develop an integrated and extensible framework to address existing and future attacks on WiFi networks. Specifically, we focus our efforts on an integrated set of new components that allow a WiFi network operator to measure and analyze WiFi and VoWLAN activity, and in real-time to identify and defend against MAC- and IP-layer attacks on that infrastructure. Our plan includes three overlapping phases: research, prototype development, and deployment on Dartmouth's campus-wide wireless network; the third phase is an option.
Understanding PLACE (Privacy in Location-Aware Computing Environments)
Prof. David Kotz,
Prof. Andrew Campbell
Digital technology plays an increasing role in everyday life, and this trend is only accelerating. Consider daily life five years from now, in 2010: we will each be surrounded by far more digital devices, mediating far more activities in our work, home, and play; the boundary between cyberspace and physical space will fade as sensors and actuators allow computers to be aware of, and control, the physical environment; and the devices in our life become increasingly (and often invisibly) interconnected with each other and with the Internet. Today, typical home users struggle to maintain the security of their home computer, and have difficulty managing their privacy online. Tomorrow, these challenges may become unimaginably complex. This 18-month project studies, and begins to address, the security and privacy challenges involved in developing this world of Digital Living in 2010.
Interactive Algorithms for Appearance Design
The use of synthetic images has become an integral part of engineering, science, design, fine art, entertainment, and other disciplines. While advances in software algorithms and hardware architectures have made synthetic images more readily available, the human labor and technical expertise required to create models suitable for image synthesis remains its major limiting factor.
To address this issue, we are devloping interactive and artist-friendly algorithms for appearance design. This research led to various theoretical results and practical applications in the areas of interactive realistic rendering, artist-friendly user interfaces and visual perception.
Towards Effective PKI
In a distributed world, how can a stakeholder verify the identity (or other relevant properties) of a remote party?
In the emerging information infrastructure, multiple parties spanning multiple organizations have various opinions about what they might trust, in what contexts. To be effective, the underlying mechanics for transmitting and expressing assertions about these parties needs to be able to provide the right parameters to accommodate this multiplicity of views.
Because it can enable secure communications between parties who do not share a secret beforehand, public key cryptography is a natural and perhaps unique building block. Achieving this vision in the real world, however, requires public key infrastructure (PKI). In our lab, we are exploring a number avenues to make PKI effective in the real world.
Trusted Hardware
A trusted third party (TTP) can make it easier to solve multi-party security problems. However, using a TTP in a design has been akin to invoking magic or fairies: tools not possible in the real world.
However, in the last decade, techniques have emerged that can provide foundations for TTPs based in hardware. In our lab, we are exploring ways of building effective trustworthy platforms founded on these techniques and using these platforms for hardware-based TTPs in real-world applications.
MCMC and the Theory of Computing
The basic problem in the Theory of Computing is do determine what kinds of problems can be efficiently solved by computer; in other words, what can algorithms do or not do.
In the 70's, theorists uncovered a wide range of "hard" decision and computation problems which are all intractable --- except in the (unlikely) event that they were all tractable! Since then, exciting new techniques involving probabilistically checkable proofs have established that many quantities are as hard to approximate as they are to compute exactly.
Ironically, however, at about the same time theorists discovered a powerful mathematical tool which has greatly expanded the range of quantities which we can approximate efficiently. Included are volumes of high-dimensional objects, partition functions in statistical physics, the permanent of a matrix, the number of linear extensions of an ordered set, generation of contingency tables (used by actuaries to compute insurance rates) and many more. The method, called MCMC (Markov chain Monte Carlo), entails randomly sampling the objects being counted by starting with a non-random object and moving to a random neighboring object.
The mathematical crux of this method is proving "rapid mixing", i.e., showing that the process reaches a random object in sufficiently short time. Practically every branch of mathematics has contributed to the delightful variety of ways that have been devised to show rapid mixing in its many guises.
Shown in the picture is a configuration of the Widom-Rowlinson (WR) model of statistical physics, generated by MCMC. The WR model simulates two gases (here, with red and green molecules), under the constraint that differing molecules may not occupy adjacent points on a grid.