CS Department Colloquium Series

Since the 1960s at the latest, the computer has been capable of digitally synthesizing any perceivable sound. However, in a live context, human-computer interfaces limit the bandwidth and quality of the interaction between the performer and the sound synthesizer. This talk focuses on physical interfaces for music, which operate according to the laws of physics to seamlessly and intimately connect musicians with sound synthesizers. In particular, we study how to design interfaces that assist a performer in making musical gestures. For example, the haptic drum provides a performer's drumstick with an extra push every time that the performer strikes the drum. This device allows the performer to make gestures that would otherwise be very difficult or impossible, such as arbitrarily long one-handed drum rolls and arbitrarily complex rudiments. Next, we explain how to assist a performer in accurately selecting pitches from a continuous range on a Theremin-like haptic interface. We augment it with detents allowing the performer to feel the locations of equal-tempered pitches, yet the performer can still perform arbitrary pitch inflections such as glissandi, falls, and scoops. With the help of a subject test, we demonstrate that traditional detents as well as novel force-sensitive detents can provide accuracy improvements over simpler types of haptic feedback, such as spring feedback. In closing, we relate the work to research in robotics and mixed reality.

Reconstruction of trees describing relationships among species is of vital importance to evolutionary studies. Species trees not only reveal the history of life, they also provide a framework for understanding the evolution of physiology, morphology, and cellular circuitry. Although gene sequences have proved a powerful source of evidence for inferring species trees, incorrect species trees can result when the histories of the species and the gene differ. Gene duplications, gene losses and transfer of genes from one species to another can all result in a gene tree which disagrees with the species tree. These events can be inferred and corrected for by comparing the gene and species trees, a process called reconciliation.

While reconciling a binary gene tree with a binary species tree is a well-studied, tractable problem, the standard reconciliation algorithm yields incorrect results when applied to non-binary species trees. Binary reconciliation makes simplifying assumptions about genetic variation in ancestral populations that are not justified when the species tree is non-binary. We present the first formal algorithms for reconciling binary gene trees with non-binary species trees. Our algorithms, which combine models from standard reconciliation and population genetics, have been implemented in Notung, a free, publicly available software tool available at http://www.cs.cmu.edu/~durand/Notung. I will discuss the application of these methods to resolving uncertainty in species trees, with examples from species lineages that are currently debated in the evolutionary biology literature.

Given a query where the answer is sitting on a single web page, search engines do a decent job of identifying that web page. Some queries, however, are difficult to express in text: an image is worth a thousand query terms. At other times, a textual query is sufficient, but it's difficult to type (walking, driving). And some research tasks don't have a simple answer already computed: it's necessary to synthesize an answer from multiple sources. I'll talk about some of the research projects at Google directed at solving these problems, including Google Goggles, Search by Voice, and Google Squared, and some of the other challenges that we're tackling that go beyond returning ten blue links.

Dr. Craig Nevill-Manning joined Google in 2000 as a Senior Research Scientist, responsible for developing new high-precision search techniques for use in the Google search engine. He went on to found Google's first satellite software engineering center, located in New York City, where he is currently an Engineering Director. Nevill-Manning joined Google from the Computer Science Department of Rutgers University, where he conducted research in data compression, information retrieval and computational biology. Prior to Rutgers, Nevill-Manning was a post-doctoral fellow in the Biochemistry Department of Stanford University, where he developed eMOTIF, a software suite used by many pharmaceutical research laboratories to identify the role of particular proteins within cells.

Nevill-Manning has published 41 research papers and received a National Science Foundation Career Grant. A native of New Zealand, Nevill-Manning earned a BS in Computer Science from Canterbury University and a PhD in Computer Science from Waikato University.

Molecular sequences evolve under processes that include substitutions, insertions, and deletions (jointly called "indels"), as well as other mechanisms (e.g., duplications and rearrangements). The inference of the evolutionary history of these sequences has thus been performed in two stages: the first estimates the alignment on the sequences, and the second estimates the tree given that alignment. While such methods seem to work well on relatively small datasets, these two-stage approaches can produce highly incorrect trees and alignments when applied to large datasets, or ones that evolve with many indels. In this talk, I will present a new method, SATe, that my lab has been developing that uses maximum likelihood to estimate the alignment and tree at the same time, and that can be used to analyze datasets with up to 1000 sequences on a desktop in 24 hours. Our study, using both real and simulated data, shows that this method produces much more accurate trees than the current best methods.

Tandy Warnow is Professor of Computer Sciences at the University of Texas at Austin. Her research combines mathematics, computer science, and statistics to develop improved models and algorithms for estimating complex and large-scale evolutionary histories in both biology and historical linguistics. Tandy received her PhD in Mathematics at UC Berkeley under the direction of Gene Lawler, and did postdoctoral training with Simon Tavare and Michael Waterman at USC. She received the National Science Foundation Young Investigator Award in 1994, and the David and Lucile Packard Foundation Award in Science and Engineering in 1996. Tandy is a member of five graduate programs at the University of Texas, including Computer Science; Ecology, Evolution, and Behavior; Molecular and Cellular Biology; Mathematics; and Computational and Applied Mathematics. She is also the director for the multi-disciplinary CIPRES (Cyber-Infrastructure for Phylogenetic Research) Project, currently funded by the NSF under their Information Technology Program.

PlanetLab was originally designed to be a realistic testbed for networking and distributed systems research. It has served that role quite well. More recently, however, it has also become a practical platform for rapidly deploying (and then effectively managing) network services that have value to a wide-range of user communities (and a diverse set of network environments).

This talk describes three such deployments: (1) providing web connectivity to remote villages and schools; (2) capturing gold-standard measurements of broadband connectivity in the US; and (3) supporting high-speed content distribution in a Telco access network.

Assertions are widely used for runtime checking of software correctness, and increasingly used for compile time checking of simple properties like array index bounds. Structural integrity of pointer based data structures and design patterns often involves recursively defined properties which are costly to check at runtime and which appear to be unsuited to static checking using fully automated theorem provers. Remarkably, judicious use of ghost state lets programmers express recursive properties in pure first order logic and successfully use fast provers based on SAT solving. In this talk I will introduce the technique in elementary terms, for programmers, who may find it immediately useful in testing. I will also outline research questions about how to use the technique in frame conditions, in refactoring, in foundational proofs, in refinement types, in terms of aspects, and in checking information flow properties.

Over time PlanetLab has evolved from a centrally-administered testbed to a federation of regional testbeds that are operated independently. The PlanetLab software is also freely available, which has allowed many organizations to bring up their own "private" PlanetLabs. For most private PlanetLabs, a barrier to entering the federation is the inability to express access and allocation policies for their own resources, and the lack of tools to communicate, analyze, and enforce those policies. In the first part of my talk, I will present an overview of the PlanetLab federation. Next I will focus on VINI, a private PlanetLab we have deployed in Internet2 and NLR, and which is intended for evaluating new network architectures. Finally, I will describe a tool ("sfatables") we have built for expressing and enforcing resource allocation policies. Our approach was designed to enable VINI to federate with PlanetLab, but it is general enough to accommodate a diverse collection of computing facilities.

This talk describes joint work with Larry Peterson, Sapan Bhatia, Jennifer Rexford, and Nick Feamster.

This talk introduces a new class of methods called "behavioral blacklisting", which identify spammers based on their network-level behavior. Rather than attempting to blacklist individual spam messages based on what the message contains, behavioral blacklisting classifies a message based on how the message itself was sent (spatial and temporal traffic patterns of the email traffic itself). Behavioral blacklisting tracks the sending behavior of an email sender from a wide variety of vantage points and establishes "fingerprints" that are indicative of spamming behavior. Behavioral blacklisting can apply not only to email traffic, but also to the network-level behavior of hosting infrastructure for scam or phishing attacks. First, I will present a brief overview of our study of the network-level behavior of spammers. Second, I will describe two behavioral blacklisting algorithms that are based on insights from our study of the network-level behavior of spammers. Finally, I will describe our ongoing work applying similar behavioral detection techniques to detecting both online scam hosting infrastructure and phishing attacks.

Bio
Nick Feamster is an assistant professor in the College of Computing at Georgia Tech. He received his Ph.D. in Computer science from MIT in 2005, and his S.B. and M.Eng. degrees in Electrical Engineering and Computer Science from MIT in 2000 and 2001, respectively. His research focuses on many aspects of computer networking and networked systems, including the design, measurement, and analysis of network routing protocols, network operations and security, and anonymous communication systems. He recently received the Presidential Early Career Award for Scientists and Engineers (PECASE) for his contributions to cybersecurity, notably spam filtering. His honors include a Sloan Research Fellowship, the NSF CAREER award, the IBM Faculty Fellowship, and award papers at SIGCOMM 2006 (network-level behavior of spammers), the NSDI 2005 conference (fault detection in router configuration), Usenix Security 2002 (circumventing web censorship using Infranet), and Usenix Security 2001 (web cookie analysis).

Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, in real time, and with very low storage overhead.

We give the first theoretical analysis of several underlying algorithms on a non-trivial class of networks. To do this, we introduce the notion of highway dimension. Our analysis works for networks with low highway dimension and gives a unified explanation of good performance for several seemingly different algorithms.

Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck

With the field of computational linguistics' empirical revolution of the 1990s came the realization that human intuitions about language are insufficient for accurate and robust natural language technologies. The move from hand-written, rule-based models to data-driven techniques led to huge advances, yet we still leaned on human intuition for constructing annotated linguistic datasets. Despite major advances in this paradigm (some of which we'll discuss in this talk), we now know that, in the wild world of real and diverse linguistic data, natural language technology raised on expert-made annotations remains insufficient for real, robust applications.

In this talk we adopt the premise that unsupervised learning will, in the long run, be the way forward for learning computational models of language cheaply. We focus on dependency syntax learning without trees, beginning with the classic EM algorithm and presenting several ways to alter EM for drastically improved performance using crudely represented "knowledge" of linguistic universals. We then present more recent work in the empirical Bayesian paradigm, where we encode our background knowledge as a prior over grammars, applying inference to obtain hidden structure. Of course, "background knowledge" is still human intuition. We argue, however, that by representing this knowledge compactly in a prior distribution--far more compactly than the many decisions made in building treebanks--we can experimentally explore the connection between proposed linguistic universals and unsupervised learning.

This talk includes discussion of joint work with Shay Cohen, Dipanjan Das, Jason Eisner, Kevin Gimpel, Andre Martins, and Eric Xing.