Personal tools
Faculty Candidate Talks
-
Measuring and Understanding High-Speed Networks
Date: Apr 07, 2011
Time: 12:00 PM
Location: 4760 Boelter Hall -
***Refreshments at 11:50am***
Candidate: Daniel Freedman – Cornell UniversityAbstract:
Systems and networks have grown increasingly complex over the past four decades. The four ARPANET hosts of 1969 have been transformed into a global Internet of staggering size, connectivity, and usage. This evolution has led to the Internet displaying emergent behavior, which necessitate empirical measurement, rather than intuition, to understand. The networking literature has a rich tradition of these measurements, focusing upon either the structure of the Internet or its traffic characteristics. However, existing techniques can no longer obtain instantaneous traffic measurements with accuracy and reproducibility at high-speeds --- an inadvertent casualty of the architectural evolution of networks and systems over the past decade.
To address this, we design and implement BiFocals, a novel class of high-speed and high-precision network instrumentation. We apply our tool to perform the first exact packet-timing measurements of a network path, capturing 10 Gigabit Ethernet packets in flight on optical fiber over the wide-area. Through principled design, we improve timing precision by two to six orders of magnitude over existing techniques. Our observations contest some common assumptions about the behavior of wide-area networks and the relationship between their input and output traffic flows. Further, we identify and characterize emergent packet chains as a mechanism to explain previously observed anomalous packet loss on receiver endpoints of such networks.
I conclude by discussing our current efforts toward the next-generation of BiFocals instrumentation, as well as progress in achieving massive improvements in cost, size, and convenience that presage more wide-spread adoption of this technique. Finally, given such an instrument, I outline some open questions in networking research that should thus prove tractable.
-
Machine-Assisted Concurrent Programming
Date: Mar 31, 2011
Time: 12:00 PM
Location: 4760 Boelter Hall -
***Refreshments at 11:50am***
Candidate: Martin Vechev – IBM T.J. Watson Research Center
Abstract:Virtually all chips today are built with an increasing number of processor cores. To leverage these hardware trends, all future software will have to be concurrent.
The main challenge in developing reliable concurrent software is that a programmer is forced to coordinate a fantastic number of possible interactions. Manual coordination of these interactions (e.g., via locks) has proven to be extremely time consuming, and brittle, often resulting in programs that are incorrect, do not fully utilize the underlying computational resources, or both.
In this talk, I will present new techniques that harness the growing power of modern hardware and the increasing maturity of formal methods to simplify the process of program construction: in essence, given a concurrent program that violates a desired property, the techniques will analyze the (possibly infinite-state) program and attempt to automatically repair it by synthesizing the necessary synchronization.
A tool implementing these techniques has been successfully applied to a variety of challenging problems: from discovering tricky synchronization under weak memory models, to enforcing general atomicity properties, to obtaining new concurrent data structures and memory management algorithms.
-
Regaining Control Over Mobile and Cloud Data
Date: Mar 29, 2011
Time: 12:00 PM
Location: 4760 Boelter Hall -
***Refreshments at 11:50am***
Candidate: Roxana Geambasu – University of WashingtonAbstract:
Emerging technologies, such as cloud and mobile computing, offer previously unimaginable global access to data; however, they also threaten our ability to control the use of our data, its lifetime, accessibility, privacy, management properties, etc. My research focuses on restoring to users control they've ceded to the cloud and mobile devices. In this talk I will describe two examples of this work. First, I'll present Keypad, an auditing file system for theft- and loss-prone mobile devices that permits users to track and control accesses on their mobile data, even after a device has been stolen.
Second, I'll describe Vanish, a global-scale distributed-trust system that allows users to cause all copies of desired Web data objects, online or offline, to simultaneously self destruct at a specified time. A common thread of these efforts is the integration of systems and crypto techniques to solve new problems in data management brought on by technological change.
-
Computational Regulatory Genomics and Epigenomics in Human, Fly, and Yeast
Date: Mar 17, 2011
Time: 12:00 PM
Location: 4760 Boelter Hall -
***Refreshments at 11:50am***
Candidate: Jason Ernst - MITAbstract:
Advances in high-throughput technologies such as DNA sequencing are enabling the generation of massive amounts of biological data. This data is providing unprecedented opportunities to gain a systematic understanding of the genome of organisms and the regulation of genes encoded in them, but calls for new computational approaches for its analysis.
To address these challenges, I have developed computational methods for genome interpretation and for understanding gene regulation. (1) I developed a clustering method, STEM, for the analysis of short time series gene expression data, and initially applied it to data on immune response in human. STEM has since become a widely used method in many species and contexts. (2) I developed DREM, a method for integrating time series gene expression data with transcription factor-gene interactions, which reveals gene regulation temporal dynamics, which I applied originally in yeast and most recently in the context of the Drosophila modENCODE project. (3) I developed a method for predicting targets of transcription factors across the human genome by integrating sequence, annotation, and chromatin features, given the increasing availability of epigenetic information on chromatin modifications. (4) To exploit epigenomic information more systematically, I developed an algorithm for discovering and characterizing biologically-significant combinations of chromatin modifications across a genome, or 'chromatin states', based on their recurring patterns across the genome. (5) I used these chromatin states to study the dynamics of epigenetic changes across nine cell types in the context of the human ENCODE project, revealing a dynamic epigenomic landscape, that reveals causal regulators for cell type-specific enhancers, and provides new insights for interpreting disease-associated SNPs from genome-wide association studies (GWAS).
These methods provide a systematic way to discern regulatory information amidst the vast non-coding space of the human genome, towards a systematic understanding of gene regulation in the context of health and disease.
-
Evolving the network layer of the Internet
Date: Mar 15, 2011
Time: 12:00 PM
Location: 4760 Boelter Hall -
***Refreshments at 11:50am***
Candidate: Katerina Argyraki – EPFLAbstract:
Changing the Internet architecture is notoriously difficult. A key reason for this difficulty is that today's Internet infrastructure is mainly built on specialized hardware. This has long been considered a prerequisite for achieving the packet-processing speeds needed in the Internet core, but makes changing the functionality of the network hard, if not impossible.
I will talk about turning the Internet into an "evolvable" network -- one that allows us to try out new network services and experiment with new protocols, without having to install new specialized equipment every time. This would enable us, for instance, to continually evolve the Internet's defense mechanisms in response to new threats, or its troubleshooting mechanisms in response to new problems. I will present RouteBricks, a new router architecture, which consists entirely of off-the-shelf PCs (and can be programmed like one), yet supports line rates of tens of Gbps. Then I will show how to use such a router architecture to deploy systematic Internet troubleshooting: I will present Retroactive Sampling, a new packet sampling technique that enables Internet users or regulators to track down packet loss and delay and accurately evaluate the performance of untrusted Internet service providers. Today, deploying such a system would require installing new hardware throughout the Internet; with evolvable network infrastructure, like RouteBricks, it would only require a software upgrade.
-
Machine Learning with Infinite Models and Finite Computation
Date: Mar 10, 2011
Time: 12:00 PM
Location: 4760 Boelter Hall -
***Refreshments at 11:50am***
Candidate: Ryan Adams – University of Toronto
Abstract:
We are undergoing a revolution in data. As computer scientists, we have grown accustomed to constant upheaval in computing resources -- quicker processors, bigger storage and faster networks -- but this century presents the new challenge of almost unlimited access to raw information. Whether from sensor networks, social computing or high-throughput cell biology, we face a deluge of data about our world. We need to parse this information, to understand it, to use it to make better decisions. In this talk, I will discuss my work to confront this challenge, developing new machine learning algorithms that are based on infinitely-large probabilistic graphical models. In principle, these infinite representations allow us to analyze sophisticated and dynamic phenomena in a way that automatically balances simplicity and complexity -- a mathematical Occam's Razor.Our computers, however, are inevitably finite, so how can we use such tools in practice? I will discuss how my approach leverages ideas from Bayesian statistics to develop practical algorithms for inference in infinite models with finite computation. I will discuss how combining a firm theoretical footing with practical computational concerns gives us tools that are useful both within computer science and beyond.
-
Vertex Sparsification
Date: Mar 08, 2011
Time: 12:00 PM
Location: 4760 Boelter Hall -
***Refreshments at 11:50am***
Candidate: Ankur Moitra - MIT
Abstract:
Suppose we are given a gigantic communication network, but are only interested in a small number of nodes (clients). There are many routing problems we could be asked to solve for our clients. Is there a much smaller network - that we could write down on a sheet of paper and put in our pocket - that approximately preserves all the relevant communication properties of the original network? As we will demonstrate, the answer to this question is YES, and we call this smaller network a vertex sparsifier.
In fact, if we are asked to solve a sequence of optimization problems characterized by cuts or flows, we can compute a good vertex sparsifier ONCE and discard the original network. We can run our algorithms (or approximation algorithms) on the vertex sparsifier as a proxy - and still recover approximately optimal solutions in the original network. This novel pattern saves both space (because the network we store is much smaller) and time (because our algorithms run on a much smaller graph).
Additionally, we apply these ideas to obtain a master theorem for graph partitioning problems - as long as the integrality gap of a standard linear programming relaxation is bounded on trees, then the integrality gap is at most a logarithmic factor larger for general networks. This result implies optimal bounds for many well studied graph partitioning problems as a special case, and even yields optimal bounds for more challenging problems that had not been studied before. Morally, these results are all based on the idea that even though the structure of optimal solutions can be quite complicated, these solution values can be approximated by crude (even linear) functions. -
Leveraging Structure to Efficiently Make Good Decisions in an Uncertain World
Date: Mar 03, 2011
Time: 12:00 PM
Location: 4760 Boelter Hall -
***Refreshments at 11:50am***
Candidate: Emma Brunskill – UC BerkeleyAbstract:
Making good sequential decisions under uncertainty is a core part of what it means to be smart. It is formally hard to solve these problems when part of the environment is hidden, and most such real problems are intractable to solve with general-purpose algorithms. Developing approaches that scale to much larger, more complex domains could lead to profound impact on applications ranging from patient treatment to mobile manipulation to computer assisted education.
In this talk I will discuss several algorithms that leverage structure common in diverse problem classes in order to efficiently make decisions in dramatically larger domains. I will present results on autonomous helicopter surveillance and share results of a field study in Bangalore, India demonstrating that an adaptive tutoring software game has the potential to increase student engagement.
