- talks - lists.cs.princeton.edu

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

Colloquium Speaker, Feb. 10, 2010- John Ousterhout
by Nicole E. Wagenblast 08 Feb '10

08 Feb '10

RAMCloud: Scalable High-Performance Storage Entirely in DRAM John Ousterhout, Stanford University 4:30pm Small Auditorium CS 105 Disk-oriented approaches to online storage are becoming increasingly problematic: they do not scale gracefully to meet the needs of new large-scale Web applications, and improvements in disk capacity have out-stripped improvements in access speed. In this talk I will describe a new approach to datacenter storage called RAMCloud, where information is kept entirely in DRAM and large-scale systems are created by aggregating the main memories of thousands of commodity servers. A RAMCloud can provide durable and available storage with 100-1000x the throughput of disk-based systems and 100-1000x lower access latency. By combining low latency and large scale, RAMClouds will enable a new class of applications that manipulate large datasets more intensively than has ever been possible before.

1 1

[Fwd: Hellenic Studies Lecture: Thursday, February 11, 2010]
by Michele J. Brown 03 Feb '10

03 Feb '10

1 0

Brighten Godfrey talk on Distributed Compact Routing Thrus 3pm
by Nicole E. Wagenblast 02 Feb '10

02 Feb '10

Title: Distributed Compact Routing Speaker: Brighten Godfrey, UIUC Time: 3pm, Thursday, Feb 4th Room: CS 302 Abstract: Common wisdom is that the way to scale networks to large size is hierarchy: routing is performed on higher level aggregates across domains, separately from routing within domains. We live with the consequences: inflated path lengths, and the use of location-dependent addresses (IP addresses in the Internet) which complicate management, mobility, and multihoming. I will present Distributed Compact Routing, a protocol which (1) guarantees scalability, in the form of roughly \sqrt{n} state for a network of n nodes; (2) guarantees approximately-shortest paths, in the form of constant stretch; and (3) routes directly on flat, location-independent identifiers. Our work builds on recent theoretical advances in the area of compact routing. Past attempts to translate these centralized algorithms to practical distributed protocols have had limited success, compromising state or stretch guarantees or assuming special topologies. Our results thus represent a significant step forward in routing technology, which we believe has direct applicability to many kinds of networks including peer-to-peer networks, Internet routing, and content-centric networks. Joint work with Ankit Singla, Kevin Fall, Gianluca Iannaccone, and Sylvia Ratnasamy.

1 0

Colloquium Speaker, Wednesday, February 3, 2010-Tandy Warnow
by Nicole E. Wagenblast 01 Feb '10

01 Feb '10

Speaker: Tandy Warnow, University of Texas at Austin Title: *Simultaneous Alignment and Phylogenetic Tree Estimation* Wednesday, February 3, 2010 4:30 PM Small Auditorium (CS 105) Abstract: 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. _______________________________________________ talks mailing list talks(a)lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/talks

1 0