- talks - lists.cs.princeton.edu

Ge Wang preFPO
by Melissa M Lawson 12 Feb '07

12 Feb '07

Ge Wang will present his preFPO on Friday February 16 at 2:00pm in Room 402. The members of his committee are: Perry Cook, advisor; Paul Lansky (Music) and Roger Dannenberg (CMU), readers; Andrew Appel and Brian Kernighan, non-readers. Everyone is invited to attend his talk. His abstract follows below. ------------------------------------- The ChucK Audio Programming Language ("A Strongly-timed and On-the-fly Environ/mentality") The computer has long been considered an extremely attractive tool for creating, manipulating, and analyzing sound. Its precision, possibilities for new timbres, and potential for fantastical automation make it a compelling platform for expression and experimentation - but only to the extent that we are able to express to the computer what to do, and how to do it. To this end, the programming language has served, perhaps, as the most general, and yet most precise and intimate interface between humans and computers. Furthermore, "domain-specific" languages can bring additional expressiveness, conciseness, and perhaps even different ways of thinking to the domain (e.g. sound synthesis). This thesis argues for the philosophy, design, and development of ChucK, a domain-specific programming language designed for computer music. The goal is to create a language that is "expressive" and "easy to write and read" with respect to time and parallelism, and to provide a platform for precise synthesis/analysis and rapid experimentation in computer audio. In particular, ChucK provides a syntax for representing information flow, a new time-based concurrent programming model that allows programmers to easily (and flexibly) control the flow of time in code (we call this "strongly-timed"), and facilities to develop programs "on-the-fly" - as they run. A ChucKian approach to "live coding" as a new musical performance paradigm is also described - and ultimately motivates the Audicle, a specialized graphical environment designed to facilitate on-the-fly programming, to visualize and monitor ChucK programs in real-time, and to provide a platform for building highly customizable user interfaces. The various aspects of the ChucK language (and Audicle) are evaluated in the context of computer music research, performance, and pedagogy. As part of an extensive case study, the thesis discusses ChucK as a primary teaching and development tool in the Princeton Laptop Orchestra (PLOrk), which continues to be a wonderfully useful platform to observe the effectiveness of ChucK for teaching topics ranging from programming to sound synthesis, and for crafting new instruments, compositions, and performances for computer-mediated ensembles. Additional applications are also described, including classrooms, live coding "arenas", compositions and performances, user studies, and integrations of ChucK into other software systems, such as the sound design environment TAPESTREA. The oral presentation shall also include a brief history of computer music and programming, and offer contrast between ChucK and other computer music languages and environments.

1 0

S Gaw preFPO
by Melissa M Lawson 09 Feb '07

09 Feb '07

Shirley Gaw will present her preFPO on Thursday February 15 at 4:30PM in Room 302 (note room). The members of her committee are Ed Felten, advisor; Paul Dourish (UC Irvine) and Brian Kernighan, readers; Perry Cook and Olga Troyanskaya, non-readers. Everyone is invited to attend her talk. Her abstract follows below. ------------------------------------- Human factors are considered one of the "weakest links" in computer security. That is, there is a gap between the theoretical security of a system and the practical security of a system. My thesis addresses this gap by understanding how users observe or avoid secure practices. The central argument of my thesis is that a sociological approach to computer security is a missing but necessary foundation for addressing the "weakest link" in secure systems. While we may have intuitions about human behavior, simplistic models of users fail to capture the underlying complexity of their practices in real situations, including both their adoption of security technologies and their implementation of security policies. I will illustrate this by discussing results from three studies investigating the human side of computer security: use of encrypted e-mail in an activist organization, password management practices of undergraduates, and privacy concerns of knowledge workers. Finally, I will discuss how results from sociological approaches can inspire design for novel systems. We are working on using the results from the encrypted e-mail study to design a communication system where interaction relies on implicit cues of user involvement and trust built over time.

1 0

Optimization Techniques in Linux Development Feb 20-22
by Chrissy Colvin 07 Feb '07

07 Feb '07

Registration is required and space is limited. To register, email ccolvin(a)cs.princeton.edu DATES: February 20, Friend 004 February 21, Friend 009 February 22, Friend 004 TIME: 4:30 pm - 7:00 PM Linux Performance measurement and optimization is a black art: to achieve results, knowledge of a varied set of tools and insight into the system's internals are required to successfully conclude the investigation with clear, irrefutable evidence of the responsible bottleneck. The speaker will take the audience through a marathon demonstration of the primary benchmarking tools, highlighting their features, pitfalls and limits, while at the same time describing the underlying system mechanisms interrelating with what is being measured. Initially focusing on the performance of the whole system, the discussion will then shift to performance measurement and optimization of a specific process, covering the approaches available to benchmark and tune programs running natively on the system or inside a virtual machine. Three sessions will cover the necessary theory and introductory hands-on practice, as we cover both System and Network performance problems. Instructor: Federico Lucifredi, Harvard University Federico Lucifredi is the maintainer of the man suite, the primary documentation-delivery tool under Linux, a graduate student at Harvard University, and a software-engineer-turned-manager at Novell corporation. Previously, Federico has been a CTO and a network software architect '.com' and embedded Linux startups, and he has spent two years teaching in Boston University's graduate and undergraduate programs, while simultaneously consulting for MIT. He is a frequent speaker at user group and conference events, notably the LinuxWorld and the IMPlanet conferences, where he was a panelist representing the jabber community. Federico is a recognized expert in computing performance issues, and consults pro-bono with Standard and Poor's clients interested in Free/Open Source technical and strategic issues, while currently participating in the GPL v3 drafting process in the large-corporation panel. Registration is required and space is limited. To register, email ccolvin(a)cs.princeton.edu DATES: February 20, Friend 004 February 21, Friend 009 February 22, Friend 004 TIME: 4:30 pm - 7:00 PM

1 0

M Dudik preFPO
by Melissa M Lawson 07 Feb '07

07 Feb '07

Miro Dudik will present his preFPO on Friday February 9 at 10AM in Room 402. The members of his committee are Rob Schapire, advisor; David Blei and Stephen Phillips (AT&T), readers; Moses Charikar and Olga Troyanskaya, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------- Maximum entropy, generalized regularization, and modeling species habitats Maximum entropy (maxent) approach, equivalent to maximum likelihood, is a widely used method for estimating probability distributions. However, when trained on small datasets, maxent is likely to overfit. Therefore, many smoothing techniques were proposed to mitigate overfitting. In my dissertation, I propose a unified treatment for a large and general class of smoothing techniques including L1 and L2 regularization. As a result, it is possible to prove non-asymptotic performance guarantees and derive novel regularizations based on structure of the sample space. To obtain solutions for a large class of maxent problems, I propose new algorithms derived from boosting and iterative scaling. Convergence of these algorithms is proved using a novel method, which unifies previous approaches based on information geometry and compactness. As an application of maxent, I discuss an important problem in ecology: modeling distributions of biological species. Regularized maxent fits this problem well and offers several advantages over previous techniques. In particular, it addresses the problem in a statistically sound manner and allows principled extensions to situations when data is collected in a biased manner or when we have access to data on many related species. The utility of maxent is demonstrated on large real-world datasets.

1 0

C Myers preFPO
by Melissa M Lawson 05 Feb '07

05 Feb '07

Chad Myers will present his preFPO on Friday February 9 at 3:30 PM in Carl Icahn Lab Room 200. The members of his committee are: Olga Troyanskaya, advisor; Kai Li and David Botstein (MolBio, Genomics), readers; SY Kung (ELE) and Leonid Kruglyak (EEB, Genomics), non-readers. Everyone is invited to attend his talk. His abstract follows below. --------------------------------------- Title: Context-sensitive methods for learning from genomic data Abstract: Recent developments in biotechnology have enabled high-throughput measurement of several complementary cellular phenomena. The wealth of data generated by such technology promises to support computational prediction of network models, but so far, successful approaches that translate these data into accurate, experimentally testable hypotheses have been limited. My thesis focuses on machine learning and signal processing approaches that utilize contextual clues that often accompany biological data to extract useful information and make precise predictions. First, my thesis describes methods for using microarray technology to detect chromosomal aberrations. Amplification and deletion of portions of chromosomes often serves as a mechanism of rapid adaptation and have been associated with numerous cancers. Accurate and precise identification of when and where these changes occur will help us understand this important adaptive mechanism and enable steps towards effective cancer treatment. I discuss my solution to this problem, ChARM (Chromosomal Aberration Region Miner), a statistical signal processing approach based on expectation-maximization that uses chromosome context information to accurately identify even subtle chromosomal changes from either gene expression or CGH microarray data. Second, I have addressed the more general problem of integrating diverse types of functional genomic data (e.g. gene expression, protein-protein interactions, genetic interactions, sequence, and protein localization data) to understand gene function and predict biological networks. I discuss a system we have developed for integration of these diverse data and user-driven network inference. My key contribution in this area is the notion of query context-sensitive prediction. This idea is based on the observation that most experimental technologies capture different biological processes with varying degrees of success, and thus, each source of genomic data will vary in relevance depending on the biological process one is interested in predicting. Other key contributions of this work are the data visualization approaches that support intelligent, expert browsing of genomic data, which is a largely unexplored, but powerful paradigm in bioinformatics applications. I discuss evaluation of these methods and examples of biological validation, where we have used our system to characterize several new genes. Finally, my thesis addresses the question of how to use machine learning and other bioinformatics methods to direct large-scale genomic experiments. Until now, most bioinformatics methods have been applied downstream of data-generating experiments, serving mainly as tools for analysis. I discuss methods for directing large-scale experiments in the context of whole-genome genetic interaction screens. We have applied these methods in collaboration with experimental labs, and we demonstrate that such approaches enable more efficient use of high-throughput technology and, ultimately, help us to learn more novel biology.

1 0

P Shilane preFPO
by Melissa M Lawson 02 Feb '07

02 Feb '07

Phil Shilane will present his preFPO on Thursday February 8 at 10AM in Room 402. The members of his committee are; Thomas Funkhouser, advisor; Adam Finkelstein and Szymon Rusinkiewicz, readers; Andrea LaPaugh and Kai Li, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------------------------- Title: Shape Distinction for 3D Model Retrieval Abstract: In recent years, there has been enormous growth in the number of 3D models and their availability to a wide segment of the population. Examples include the National Design Repository which stores 3D computer-aided design (CAD) models for tens of thousands of mechanical parts, the Protein Data Bank that has atomic positions for tens of thousands of protein molecules, and the Princeton Shape Benchmark with 36,000 everyday objects represented as polygonal surface models. Given the availability of 3D data, a key problem is searching through models efficiently. Finding similar objects in a database can provide information for protein analysis or to identify objects in a robotic-vision system. As another example, by searching a database of models, even a novice user could easily create new CAD objects or graphics models by assembling them from examples, instead of the complicated task of creating models from scratch. While previous work has approached the 3D retrieval problem by creating global feature vectors for each object or by creating numerous local feature vectors, my work focuses on "distinctive" regions of a surface that distinguish a shape from objects of a different class. Distinctive regions are analyzed based on performing a shape-based search using each surface region as a query into a database. Distinctive regions of a surface have shape consistent with objects of the same type and different from objects of other types. For a classified database of models, distinction can be analyzed in a pre-processing phase, but I also show that a likelihood model can predict distinction for new shapes based on a training set. Using a priority-driven search technique that focuses on the most distinctive regions of each shape provides better search results than any previously published work. While the current definition of distinction is based on shape retrieval, it is useful for other graphics applications such as mesh visualization, icon generation, and mesh simplification. I also propose a new methodology to analyze shape retrieval by creating a common dataset of classified 3D models and software tools called the Princeton Shape Benchmark (PSB). The freely available PSB includes the models, classification, annotations for each model, and a suite of software tools to evaluate and analyze shape-retrieval results. My experiments with these classifications expose different properties of shape-based retrieval methods that were not previously known. As an example, shape descriptors that had poor performance when considering all models in the PSB actually had the best performance on certain classes of models. Perhaps the largest contribution of the PSB is that the dataset and software tools make it easier to perform shape-similarity research. Undergraduate computer graphics courses, senior thesis work, and doctoral projects have experimented with the 3D models and tools making the PSB a de-facto standard for measuring shape-similarity methods in the Computer Graphics community.

1 0

D Dantas preFPO
by Melissa M Lawson 30 Jan '07

30 Jan '07

Daniel Dantas will present his preFPO at 10AM on Tuesday, February 6 in Room 402. The members of his committee are David Walker, advisor; Andrew Appel, Stephanie Weirich, readers; Ed Felten, and David August, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------ My thesis extends functional programming languages with aspect-oriented features, primarily to explore aspect-oriented enforcement of security policies. First, my thesis examines an aspect-oriented implementation of the Java security mechanism, which requires the security advice to be triggered by functions with diverse argument and return types. My thesis presents a new language, AspectML, that allows a programmer to define type-safe polymorphic advice using pointcuts constructed from a collection of polymorphic join points. I then compare my AspectML implementation of the Java security mechanism against the existing Java implementation. Second, in ordinary aspect-oriented programming, security and other advice added after-the-fact to an existing codebase can disrupt important data invariants and prevent local reasoning. Instead, my thesis shows that many common aspects, including security advice, can be implemented as harmless advice. Harmless advice uses a novel type and effect system related to information-flow type systems to ensure that harmless advice cannot modify the behavior of mainline code. To demonstrate the usefulness of harmless advice for security, I implemented many of the security examples used by the Naccio execution monitoring system by Evans and Twyman as harmless advice. Finally, my thesis expands the harmless advice specification to allow programmers to create interference policies for system libraries to define how those libraries can be used by aspects. These policies use a selection of compile-time type checking and run-time monitoring to enforce the desired definition of harmlessness on the aspect-oriented program. My thesis formalizes an idealized file IO system and proves that an interference policy specified by our policy language can continue to enforce our original view of harmlessness for advice that uses file IO.

1 0

S Kale preFPO
by Melissa M Lawson 23 Jan '07

23 Jan '07

Satyen Kale will present his preFPO on Tuesday January 30 at 1PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Rob Schapire, readers; Bernard Chazelle and Boaz Barak, nonreaders. Everyone is invited to attend his talk. His abstract follows below. _____ Title: Efficient Algorithms using the Multiplicative Weights Update method Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such problems, quite often the running time of these algorithms is very high. Designing simpler and more efficient algorithms is important for practical impact. In my talk, I will describe applications of the Multiplicative Weights Update method in the design of efficient algorithms for various optimization problems. This method, which was repeatedly discovered in quite diverse fields, is an algorithmic technique which maintains a distribution on a certain set of interest, and updates it iteratively by multiplying the probability mass of elements by suitably chosen factors based on the distribution. The central result of my thesis is a generalization of the method to the setting of symmetric matrices rather than real numbers. I will describe the following applications of the resulting Matrix Multiplicative Weights algorithm: 1. The first truly general, combinatorial, primal-dual method for designing efficient algorithms for semidefinite programming. Using these techniques, we obtain significantly faster algorithms for obtaining O(sqrt{log n}) approximations to various graph partitioning problems, such as Sparsest Cut, Balanced Separator in both directed and undirected weighted graphs, and the Min UnCut problem. 2. An O*(n^3) time derandomization of the Alon-Roichman construction of expanders using Cayley graphs. 3. An O*(n^3) time deterministic O(log n) approximation algorithm for the quantum hypergraph covering problem. 4. A simpler proof of a result of Aaronson that the gamma-fat-shattering dimension of quantum states on n qubits is O(n/gamma^2). I will also briefly mention the following algorithmic applications of the classical Multiplicative Weights Update method: 1. Fast algorithms for approximately solving several families of semidefinite programs, which beat interior point methods. 2. O(sqrt{log n}) approximation to the Sparsest Cut in graphs in O*(n^2) time.

1 0

A Karagiozova preFPO
by Melissa M Lawson 18 Jan '07

18 Jan '07

Adriana Karagiozova will present her preFPO on Thursday January 25 at 3PM in Room 402. The members of her committee are Moses Charikar, advisor; Bernard Chazelle, Bob Tarjan, readers; Boaz Barak, Bob Sedgewick, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. -------------------------------------- Aspects of Network Design and Metric Space Embeddings In this talk I will present results on several problems in network design and metric space embeddings: 1) Multicommodity buy-at-bulk network design We seek to design a cheap network that satisfies the demands between the terminals of multiple source-sink pairs, where the edge costs experience economies of scale. We give the first non-trivial approximation algorithm for the general case of the problem. 2) Terminal Backup Given a graph with terminals, non-terminals and edge costs we want to find a forest that connects each terminal to at least one other terminal. We give a simple polynomial time algorithm that finds the cheapest such forest. In the process we show that a version of 3D matching, useful for tasks that involve splitting into groups of at least two members, is solvable in polynomial time. 3) Metric Ramsey phenomena A Ramsey theorem on metric spaces asks if given an arbitrary metric space, what is the size of the largest subspace that embeds into $\ell_p$ with distortion at most some target $\alpha$. Previous work shows a phase transition at $\alpha = 2$ for $p > 2$. We show that such a phase transition occurs at $\alpha = 2$ for all $p \geq 1$. 4) Embedding series-parallel graphs into $\ell_1$ We give an embedding of any n-point series-parallel metrics into $\ell_1$ with distortion O(\sqrt{\log n / \log s}), where every coordinate of the embedding is s-Lipschitz. Using this embedding we obtain various other results, among which is matching the dimension-reduction lower bound of Brinkman and Charikar.

1 0

K Park FPO
by Melissa M Lawson 17 Jan '07

17 Jan '07

KyoungSoo Park will present his final public oral on Wednesday January 24 at 2PM in Room 402. The members of his committee are: Vivek Pai, advisor: Larry Peterson and Jennifer Rexford, readers; Brian Kernighan and Andrea LaPaugh, nonreaders. A copy of his thesis, "Towards Highly Reliable and Scalable Distributed Systems" is on display in Room 310. Everyone is invited to attend his talk.

1 0