CS Department Colloquium Series

Matching markets appear in many different scenarios, from college admissions to job search. In the simplest, the deferred acceptance of Gale and Shapley provides a stable solution (also known as a stable marriage) to these problems. It also has the desirable property that for the ``proposing side" it is a dominant strategy to behave truthfully.

In this talk, I will focus on a couple of more involved matching markets. The first will be assigning doctors to residencies when there are two body problems. We will discuss the Match, show impossibility results, and present new matching algorithms that satisfy the above properties in a large market . The second will be Internet ad auctions with budgets, where we match between advertisers and slots on the web-page.

Based on Joint works with Itai Ashlagi, Mark Braverman, Ron Lavi and Moshe Tennenholtz

Graphical models such as Markov random fields have been successfully applied to a wide variety of fields, from computer vision and natural language processing, to computational biology. Exact probabilistic inference is generally intractable in complex models having many dependencies between the variables.

In this talk, I will discuss recent work on using linear programming relaxations to perform approximate inference. By solving the LP relaxations in the dual, we obtain efficient message-passing algorithms that, when the relaxations are tight, can provably find the most likely (MAP) configuration.

Our algorithms succeed at finding the MAP configuration in protein side-chain placement, protein design, and stereo vision problems. More broadly, this talk will highlight emerging connections between machine learning, polyhedral combinatorics, and combinatorial optimization.

Advances in sensing and computing capabilities of embedded systems allow accurate and precise measurement of human motion, enabling studies of diverse physical tasks and the development of sophisticated human-computer interfaces driven by gestural input.

Leveraging prior work in the development of interactive music controllers, a wireless measurement system comprised of inertial, force, and position sensors, is implemented on a violin and bow in order to capture the primary bowing parameters (bow force, bow speed, and bow-bridge distance) produced during realistic performances. A study of standard bowing techniques performed by expert violinists shows that with appropriate data reduction and pattern recognition techniques, gesture data from the above sensors may be used to recognize the same technique when performed by different players, as well as to begin to discriminate different players' performances of the same techniques.

Accurate interpretation of human motion is not only useful for understanding expressive musical performance, but it is crucial for other human-computer interfaces, such as assistive mobility devices, in which ensuring safety is a chief concern. New lower limb prostheses and orthoses designed to correct gait pathologies (caused by disease or injury) include active elements that must be controlled in realtime as a function of the user's motion. Using sensing systems similar to that described above, relevant gait parameters (such as orientation, velocity, and position) may be estimated for use as control inputs for these active devices, as well as for general use in the study of gait biomechanics.

Results and current progress will be presented, and implications for future applications in new music instrument development, music performance pedagogies, and interventions for rehabilitation and augmentation will be discussed.

Diana Young is a Postdoctoral Associate in the Biomechatronics research group at the MIT Media Lab, where she contributes to the development of measurement systems that capture human locomotion for use in active lower limb prostheses. Her research interests include measurement and understanding of human motion, both functional and expressive, and the development of human-computer interfaces for rehabilitation and the enhancement of skill acquisition. For her doctoral studies on the physical dynamics of violin bowing, she designed a playable calibrated measurement system to capture and record physical bowing parameters generated by players. She has also developed several related gesture sensing systems for use in live interactive music performance by professional musicians. Her work has been featured in numerous media, including The Strad magazine, Strings Magazine, The Boston Globe, New Scientist Podcast series, and Scientific American Frontiers. Young holds a Ph.D. and M.S. in Media Arts and Sciences from MIT, a B.S. in Electrical Engineering and B.A. in Music from The Johns Hopkins University, and a Performer's Certificate in Violin from the Peabody Conservatory of Music.

Supervised learning offers a useful set of algorithmic tools for many problems in computer music composition and performance. Through the use of training examples, these algorithms offer human musicians a means to implicitly specify the relationship between low-level, human-generated control signals (such as gesturally-manipulated sensor outputs or audio captured by a microphone) and the desired computer response (such as a change in synthesis or structural parameters of dynamically-generated audio).

In my work, I explore how to most effectively enable users to interact with supervised learning algorithms to compose and perform new music. I have built a general-purpose software system for applying standard supervised learning algorithms in real-time problem domains. This system, called the Wekinator, supports human interaction throughout the entire supervised learning process, including the generation of training examples and the application of trained models to real-time inputs. Already, the Wekinator has enabled the creation of several new compositions and instruments. Furthermore, this system has enabled me to study several aspects of human-computer interaction with supervised learning in computer music. I have used the Wekinator as a foundation for a participatory design process with practicing composers, ongoing work with non-expert users in a classroom context, and the design of a gesture recognition system for a sensor-augmented cello bow.

This research has led to a clearer characterization of the requirements and goals of instrument builders and composers, a better understanding of how to design user interfaces for supervised learning in both real-time and creative application domains, and a greater insight into the roles that interaction (encompassing both human-computer control and computer-human feedback) can play in the development of systems containing supervised learning components. This work highlights how music and other creative endeavors differ from more traditional applications of supervised learning, and it contributes to a broader HCI perspective on machine learning practice.

Devices and systems for measuring real-world shape, motion, and appearance have contributed to progress in computer graphics over the last 15 years. For example, digital photography and image-based rendering have had a profound impact on rendering. Motion capture has transformed computer animation. Geometry acquisition using 3D scanners has driven developments in geometry processing. In data-driven computer graphics, we have replaced hand-modeled and procedurally-defined components with real-world measurements. Furthermore, we have developed tools to modify and edit these data-driven representations.

With these new methods in hand, computer graphics has succeeded in recreating reality on a computer screen. The next big challenge for computer graphics and interactive techniques is to expand beyond a computer display. In the next years, the field will be working on algorithms and tools that will allow us to design and automatically fabricate physical output. This trend will dramatically increase the scope of computer graphics and it will exert significant impact on our daily lives.

In my talk, I will show two instances of a process that bridges the gap between the digital and real worlds. First, I will describe a mathematical modeling of light reflection from surfaces, based on measurements of physical materials, as well as the reverse process: manufacturing physical materials with desired reflectance properties. Second, I will present an analogous process for measurement, modeling, and fabrication of objects with desired deformation behavior. Not only do these research projects showcase how the scope of computer graphics methods can be greatly extended, but they also prompt fundamental research into the representation and processing of data types that go beyond images and video.

Wojciech Matusik is a senior research scientist at Disney Research Zurich. He received a B.S. in EECS from the University of California at Berkeley in 1997, a M.S. in EECS from MIT in 2001, and a Ph.D. in 2003. In 2004, he was named one of the world's top 100 young innovators by MIT's Technology Review Magazine. He received an ACM SIGGRAPH Significant New Researcher Award in 2009. His primary research is in the field of computer graphics, with broad applications in other disciplines such as digital communications, materials science, optics, and biomechanics.

A basic assumption often made in Machine Learning is that the data we observe are independent and identically distributed. But is this really necessary? Is it even realistic in typical scenarios? A number of recent results provide guarantees for arbitrary (or even adversarially-generated) data sequences. It turns out, for a wide class of problems, the learner's performance is no worse when the data is assumed to be arbitrary as opposed to i.i.d. This result involves a nice application of the Minimax theorem, which I'll briefly describe. I'll also delve into a more challenging problem: the "bandit" setting, in which the learner receives only very little feedback on each example. It was unknown for some time whether there exists an efficient algorithm that achieves the same guarantee for non-i.i.d. data for a general class of learning/decision problems. I'll present the first known such bandit algorithm, and I'll sketch the central ideas behind the technique, borrowing several tricks from the Interior Point optimization literature.

Emerging trends in computation such as cloud computing, virtualization, and trusted computing require that computation be carried out in remote and hostile environments, where attackers have unprecedented access to the devices, the data and the programs. This poses new problems and challenges for cryptography. In this talk, I will present two such challenges, and my recent work towards solving them.

1. Protecting against Side-channel Attacks: Computing devices leak information to the outside world not just through input-output interaction, but through physical characteristics of computation such as power consumption, timing, and electro-magnetic radiation. Such leakage betrays information about the secrets stored within the devices, and has been successfully utilized to break many cryptographic algorithms in common use. These attacks, commonly called side-channel attacks, are particularly easy to carry out when the device is in the physical proximity of the attacker, as is often the case for modern devices such as smart-cards, TPM chips, mobile phones and laptops.

In the first part of the talk, I will describe my recent work that lays the foundation of leakage-resilient cryptography - the design of cryptographic schemes that protect against large classes of side-channel attacks.

2. Computing on Encrypted Data: Security in the setting of cloud computing involves a delicate balance of privacy and functionality: while the client must encrypt its data to keep it private from the server, it should also allow for the server to compute on the encrypted data. Can we simultaneously achieve these opposing goals?

In the second part of the talk, I will describe an elementary construction of a cryptographic mechanism (called a "fully homomorphic encryption scheme") that allows arbitrary computation to be performed on encrypted data.

Both these works leverage new mathematical techniques based on geometric objects called lattices.

Bio:

Vinod Vaikuntanathan is a postdoctoral fellow in the cryptography group at IBM T.J. Watson. He received a Ph.D. from MIT in 2009 under the guidance of Shafi Goldwasser. He is a recipient of the MIT Akamai Graduate Fellowship, the IBM Josef Raviv Postdoctoral Fellowship, and more recently, the MIT George M. Sprowls award for the best Ph.D. thesis in Computer Science. The focus of his research involves the dual goals of devising new mathematical tools for cryptography, as well as applying theoretical cryptography to counter practical attacks.

Successful networked systems must account for potentially competing interests: the Internet is no longer the cooperative, technological playground it once was. The protocols are the rules relegating the venue for this competition, but those rules often lack enforcement. I will present the application of economics and trusted hardware to keep participants in a networked system from deviating from the letter and spirit of a protocol.

First, I will apply economic mechanism design to keep selfish users from gaining at the expense of others. I will show that the popular BitTorrent system uses, not tit-for-tat as widely believed, but an auction to decide which peers to serve. This model captures known, performance-improving strategies, and shapes or thinking toward new, effective incentive mechanisms.

Second, I will apply trusted hardware to keep both selfish and malicious users from "equivocating," or sending semantically conflicting messages. I will present TrInc (Trusted Incrementer), a small piece of trusted hardware intended for use in large-scale distributed systems. With case studies and an implementation, I will demonstrate that TrInc is a practical primitive for protecting a wide range of systems.

These two examples together demonstrate the importance of aligning the assumptions of economics and large-scale systems. Doing so allows us to develop new mechanisms that foster cooperation among the otherwise self-interested.

Software is everywhere, and yet, extremely unreliable. One key to reliability is the design of cost-effective techniques whereby developers can formally specify essential properties of their code, and, machines can rigorously verify that the properties hold, or demonstrate corner cases where they fail. In this talk, we describe two such techniques. First, a scheme that uses logical predicates and theorem provers to automatically compute safety proofs. Second, an approach that uses random walks to find liveness bugs in distributed systems. We describe the key algorithms underlying these approaches and the resulting tools that have helped verify and find subtle defects in a variety of complex software.

Today's computers run numerous processes of different sensitivity and trustworthiness, and often the only boundary between a hostile network and sensitive data relies on flimsy confinement assumptions. The platform purports to protect processes from each other, but side channels arise from lower architectural layers, such as contention for shared hardware resources, and create inadvertent cross-talk. For example, we have shown how observing contention for the CPU cache allows an attacker to steal other users' encryption keys in a few milliseconds.

Confinement violations are especially grievous in the context of cloud computing ("infrastructure as a service"), where users acquire computational capacity in the form of virtual machines running on a service provider's shared hardware pool. Cross-talk between mutually-untrusting virtual machines running on the same hardware creates the risk of information exfiltration across machines and between users, as we have demonstrated on Amazon EC2.

These security vulnerabilities raise the challenge of achieving trustworthy computation on leaky platforms. We discuss potential solutions, including a new work on mitigating side channels using just-in-time dynamic transformation of x86 machine code.

This talk includes joint works with Saman Amarasinghe, Dag Arne Osvik, Thomas Ristenpart, Ron Rivest, Stephan Savage, Hovav Shacham, Adi Shamir and Qin Zhao.