Quick links

CS Department Colloquium Series

Some Open Questions Related to Cuckoo Hashing

Date and Time
Wednesday, September 29, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Jennifer Rexford
In this talk, we will describe cuckoo hashing, a recently developed hashing scheme that offers the benefits of very high memory utilization and worst-case constant lookup times. We then discuss recent work in the area, including theoretical bounds on performance, practical methods for improving performance, and implementations on a GPU. Along the way, we will suggest several remaining open questions.

The talk will require no prior background on cuckoo hashing, and is aimed for a wide audience, including both theory and systems.

Michael Mitzenmacher is a Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University. Michael has authored or co-authored over 150 conference and journal publications on a variety of topics, including Internet algorithms, hashing, load-balancing, erasure codes, error-correcting codes, compression, bin-packing, and power laws. His work on low-density parity-check codes received the 2002 IEEE Information Theory Society Best Paper Award and the 2009 SIGCOMM Test of Time Award. His textbook on probabilistic techniques in computer science, co-written with Eli Upfal, was published in 2005 by Cambridge University Press.

Exploring Emotion and Expression through Music Technology

Date and Time
Tuesday, April 27, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Youngmoo Kim, from Drexel
Host
Kenneth Steiglitz
Over the past few decades, advances in computing and signal processing have had a profound impact on music performance, recording, and reproduction. The universal appeal of music, however, lies in its ability to provide expression to our feelings, and the recognition or utilization of these concepts computationally remains beyond the capability of current systems. Expression and emotion are, of course, highly subjective terms, ill-suited to quantitative definition and exploration. There may be considerable disagreement among listeners regarding the emotional content of a particular piece, and the expressive intentions of a highly skilled performer can be equally difficult to quantify. But innovations in sensing, human-computer interaction, and machine learning have the potential to reveal insights into these opaque domains.

This presentation will highlight research by the Music & Entertainment Technology Laboratory (MET-lab) at Drexel University exploring music, emotion, and creative expression under the common vision of making music more interactive and accessible for both musicians and non-musicians. These projects encompass the recognition of emotion, such as a system for dynamic musical mood prediction and a collaborative web game for the collection of emotional annotations, as well as interfaces for expressive performance, including a novel electromagnetic approach to shaping the sound of the acoustic piano and a user-friendly controller for remixing music in terms of emotion. These and other MET-lab efforts are closely coupled with educational initiatives, many of which have been deployed in K-12 outreach programs in the Philadelphia region, to promote learning in Science, Technology, Engineering, and Mathematics (STEM).

Youngmoo Kim is an Assistant Professor of Electrical and Computer Engineering at Drexel University. His research group, the Music & Entertainment Technology Laboratory (MET-lab) focuses on the machine understanding of audio, particularly for music information retrieval. Other areas of active research at MET-lab include analysis-synthesis of sound, human-machine interfaces and robotics for expressive interaction, and K-12 outreach for engineering, science, and mathematics education. Youngmoo received his Ph.D. from the MIT Media Lab in 2003 and also holds Masters degrees in Electrical Engineering and Music (Vocal Performance Practice) from Stanford University. He served as a member of the MPEG standards committee, contributing to the MPEG-4 and MPEG-7 audio standards, and he co-chaired the 2008 International Conference on Music Information Retrieval (hosted at Drexel). His research is supported by the National Science Foundation and the NAMM Foundation, including an NSF CAREER award in 2007.

Matching Markets

Date and Time
Tuesday, April 20, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Avinatan Hassidim, from MIT
Host
Sanjeev Arora
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

Approximate Inference in Graphical Models using LP Relaxations

Date and Time
Monday, April 19, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
David Sontag, from MIT
Host
David Blei
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.

Measuring Human Motion: Applications in Music Interfaces and Assistive Devices

Date and Time
Wednesday, April 14, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Diana Young, from MIT Media Lab
Host
Szymon Rusinkiewicz
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.

Real-time Human-Computer Interaction with Supervised Learning Algorithms for Music Composition and Performance

Date and Time
Tuesday, April 6, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Adam Finkelstein
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.

Bridging the Gap to the Real

Date and Time
Tuesday, April 13, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Wojciech Matusik, from Disney Research Zurich
Host
Szymon Rusinkiewicz
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.

Learning, Adversaries, and Limited Feedback

Date and Time
Monday, April 12, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Jake Abernethy, from UC Berkeley
Host
Robert Schapire
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.

Side Channels and Clouds: New Challenges in Cryptography

Date and Time
Thursday, March 25, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Vinod Vaikuntanathan, from IBM T.J. Watson
Host
Moses Charikar
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.

Systems without Cooperation

Date and Time
Wednesday, March 24, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
David Levin
Host
Edward Felten
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.

Follow us: Facebook Twitter Linkedin