February 2010 - talks - lists.cs.princeton.edu

Distinguished Colloquium Speaker Wed. March 3- Rob Cook
by Nicole E. Wagenblast 01 Mar '10

01 Mar '10

Behind the Scenes at Pixar Rob Cook, Pixar 4:30pm Small Auditorium CS 105 This talk takes you behind the scenes at Pixar Animation Studios for a look at how its 3D computer graphics films are made. The process starts with the development of the story and continues with modeling the geometry, animating the characters, simulating things like water and cloth and hair, defining the look of the surfaces, putting lights in the scene, and rendering the images. Making a computer animated film requires a close collaboration between artists and technical experts in many areas of expertise and is a great example of the value of bringing different disciplines together. Rob was the co-architect and primary author of RenderMan, software that creates photo-realistic computer images. Every film nominated for a Visual Effects Oscar in the last 15 years has used RenderMan. In 2001, along with two colleagues, Rob received an Oscar for his contributions, the first ever given for software. He has also received the Steven A. Coons Award for lifetime achievement in computer graphics and was inducted into the National Academy of Engineering. Rob has a Bachelor's degree in Physics from Duke University and a Master's in Computer Graphics from Cornell University. At Cornell, he worked on simulating realistic surfaces, taking computer-generated images beyond the distinctive plastic look they had at the time. In 1981, he joined Lucasfilm / Pixar, where he developed the first programmable shader, which is now an essential part of GPUs and game engines. He was the first to use Monte Carlo techniques in computer graphics, which was essential for the simulation of complex, realistic lights and camera effects. The latter proved particularly important in the special effects industry, because it allowed computer-generated imagery to match the motion blur and depth of field of the live-action footage with which it was combined. He is currently the Vice President of Advanced Technology at Pixar.

1 1

Colloquium Speaker Monday, March 1- Eran Tromer
by Nicole E. Wagenblast 25 Feb '10

25 Feb '10

Side Channels and their Mitigation in Cloud Computing Security Eran Tromer, MIT 4:30pm Small Auditorium CS 105 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.

1 1

D Steurer preFPO
by Melissa Lawson 24 Feb '10

24 Feb '10

David Steurer will present his preFPO on Monday March 1 at 3PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Russell Impagliazzo (IAS), Boaz Barak, Moses Charikar, and Bernard Chazelle. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------------------------- On Strengths and Limits of Relaxations for Combinatorial Optimization Mathematical programming relaxations are powerful tools for solving or approximating combinatorial optimization problems. This thesis explores the strengths and limits of these tools for a selection of basic optimization problems. A central open question in this context is the Unique Games Conjecture (Khot 2002), which asserts that a certain optimization problem, called Unique Games, is hard to approximate in a certain regime. In recent years, a sequence of works established that this conjecture has profound implications: If the conjecture is true, then a certain semidefinite relaxations, called Basic-SDP, is optimal for a large range of optimization problems, in the sense that no efficient relaxation can achieve a better approximation for any of these problems. We make the following contributions towards a better understanding of the Unique Games Conjecture and semidefinite relaxations of combinatorial optimization problems: - We exhibit an optimal rounding scheme for constraint satisfaction problems (CSPs), a well-studied class of combinatorial optimization problem. The guarantee of the scheme matches the integrality gap of the Basic-SDP relaxation for every CSP. In contrast to many previous rounding algorithms, our scheme is generic and very simple. Moreover, it allows for a principled analysis. - Using our rounding scheme and a framework (Arora and Kale 2007) for solving semidefinite relaxations, we develop an approximation algorithm for CSPs whose approximation guarantee matches the integrality of the Basic-SDP relaxation and whose running time is quasi-linear. Assuming the Unique Games Conjecture, no polynomial time algorithm can have a better approximation guarantee. - We confirm the Unique Games Conjecture for a restricted model of computation given by a hierarchy of semidefinite relaxations. In particular, we show that for every CSP, the integrality gap of the Basic-SDP cannot be improved by adding a large class of valid inequalities. It was a long-standing open question whether such stronger relaxation could lead to better approximation algorithms for problems like Max-Cut or Multiway-Cut. Our result answers this question in the negative. - Finally, we establish a connection between the Unique Games Conjecture and the problem of approximating the expansion profile of graphs. In particular, we show that the Unique Games Conjecture is true if the expansion of small sets in graphs is hard to approximate in a certain regime. This result provides the first non-trivial sufficient condition for the truth of the conjecture. (Previously, only implications of the truth of the conjecture were known.) Based on joint works with Prasad Raghavendra.

1 0

Colloquium Speaker, Feb. 24, 2010- Edgar Berdahl
by Nicole E. Wagenblast 23 Feb '10

23 Feb '10

Physical Interfaces For Applications In Music Edgar Berdahl, Stanford University 4:30pm Small Auditorium CS 105 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.

1 0

Talk Friday, Feb 19: Jason Sanders of NVIDIA
by Nicole E. Wagenblast 19 Feb '10

19 Feb '10

Jason Sanders, NVIDIA Friday, February 19, 4:30 PM Small Auditorium (CS 105) Abstract: The computing industry is currently undergoing a parallel computing revolution. The era of upward-spiraling clock speeds has drawn to a close, and the era of increasing core counts is upon us. The graphics processing unit (GPU) features a massively parallel computing architecture and is well poised to figure heavily in this evolving landscape. Two programming interfaces for the GPU, CUDA C and OpenCL, are readily available. In this presentation, NVIDIA GPU architecture and its programming models are explored. Bio: Jason Sanders is currently a senior software engineer in the CUDA team. He has been at NVIDIA for over two years, where he has developed system software and most recently has completed a book on CUDA C, due to hit shelves in 2010. He received his BSE from Princeton University in 2001 and an MS from the University of California Berkeley in 2007.

1 0

M Mahmoody Ghidary preFPO
by Melissa Lawson 19 Feb '10

19 Feb '10

Mohammad Mahmoody Ghidary will present his preFPO on Wednesday February 24 at 10:30AM in Room 402. The members of his committee are: Boaz Barak, advisor; Russell Impagliazzo (IAS/UCSD) and Moses Charikar, readers; Sanjeev Arora and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below ------------------------------------------------------------ Title: Security vs Efficiency, NP-hard Primitives, and Unconditional Cryptography. Abstract: The questions that I have studied in my thesis can be divided into the following three categories: I) How efficient a (public key) cryptographic object can be while achieving a desired quantitative level of security? -We give tight lower-bounds on the efficiency of black-box constructions of two of the main public-key cryptographic objects from "random like functions": (1) public key encryption and (2) public key authentication (i.e. signature schemes). II) Since mathematical conjectures like P<>NP are necessary for the possibility of cryptography in the standard model of computation, can we build cryptographic primitives solely by assuming P <> NP, or do we need stronger assumptions? -For some cryptographic primitives such as collision resistant hash functions we prove that basing them on P<>NP through a black-box reduction has surprising implications about the prover complexity of proving co-NP. Also for the more general question of basing average-case hardness of NP on its worst-case hardness we present a connection to the question of whether SAT has program checkers. III) Which non-standard models offer us unconditional security, while being implementable in real life? -We study the possibility of achieving unconditionally secure protocols for the main cryptographic tasks in the model of stateless tokens of Katz. We present unconditionally secure commitment schemes and efficient zero-knowledge proof systems for NP which use only one token and fall into the much simpler model of "Interactive PCP" by Kalai-Raz. We also prove that unconditionally secure oblivious transfer is not possible in the full general form of the stateless token model.

1 0

Fwd: Colloquium Speaker, Feb. 24, 2010- Edgar Berdahl
by Nicole E. Wagenblast 19 Feb '10

19 Feb '10

Physical Interfaces For Applications In Music Edgar Berdahl, Stanford University 4:30pm Small Auditorium CS 105 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.

1 0

Colloquium Speaker, Thrus Thursday, Feb. 18, 2010-Craig Nevill-Manning
by Nicole E. Wagenblast 16 Feb '10

16 Feb '10

Show and Tell, Search and Research Craig Nevill-Manning, Google Thursday, 4:30pm Small Auditorium CS 105 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.

1 0

Colloquium Speaker Feb. 17, 2010- Dannie Durand
by Nicole E. Wagenblast 15 Feb '10

15 Feb '10

Who are your closest relatives? Algorithms for reconciling non-binary species trees Dannie Durand, Carnegie Mellon University 4:30pm Small Auditorium CS 105 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.

1 1

4:30pm Thu Feb 18 talk by Craig Nevill-Manning from Google NYC on new research on search at Google
by Jennifer Rexford 11 Feb '10

11 Feb '10

Speaker: Dr. Craig Nevill-Manning, Google NYC Title: Show and Tell, Search and Research Date/time: 4:30pm CS 105 (small auditorium) Abstract: 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.

1 0