- talks - lists.cs.princeton.edu

H Yu preFPO
by Melissa Lawson 18 Apr '11

18 Apr '11

Harlan Yu will present his preFPO on Friday April 22 at 2PM in the CITP Conference Room, 3d floor, Sherrerd Hall. The members of his committee are: Ed Felten, advisor; Jen Rexford and Beth Noveck (NYU Law School), readers; Mike Freedman and Matt Salganik (SOC), nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------- Title: Designing Software to Shape Open Government Policy Abstract: An open government is fundamental to democratic societies. Openness enables citizens to make well-informed electoral choices and to hold the government accountable for its actions, and it promotes trust between the government and its people. Modern advances in computing and communications technologies have transformed what it means for a government to be open and transparent. Governments today can instantly transmit large amounts of data directly to citizens, and citizens now have vast capabilities to process and understand this information. In this dissertation, we establish the basic principles for government's use of information technology to increase openness, by focusing on the publication of raw machine-processable datasets. We then discuss how the design of software can help guide the government toward these openness principles and eventually to changes in existing policies, processes or both. We consider two projects aimed at creating such changes at the federal level. The first project examines the closed nature of federal court records in the United States. We describe the RECAP browser extension, which we purpose-built to liberate court documents in a distributed and collaborative way, and show how its core design features were essential to its widespread adoption. We address the impact our tool has made on the policy discourse, as well as the limitations of this methodology to influence desirable policy changes. The second project looks at Congress and how the current legislative process significantly hinders software-enabled transparency efforts. We show how the maintenance of the United States Code is similar to-and distinct from-revision control of source code, and we discuss the implications of these differences. We demonstrate new software tools that can, in a limited setting, provide novel benefits to the legislative process, including automatic error-detection and more efficient bill drafting. Finally, we outline what Congress should do to facilitate the development of these new transparency tools.

1 0

Colloquium Speaker, Micah Kimo Johnson, Wed April 20- 4:30pm
by Nicole E. Wagenblast 18 Apr '11

18 Apr '11

Microgeometry Capture using GelSight Micah Kimo Johnson, Massachusetts Institute of Technology Wednesday, April 20- 4:30pm Computer Science 105 GelSight is a novel sensor capable of measuring surface texture and shape at high resolutions. The sensor itself is a slab of clear elastomer covered with a reflective skin. When an object presses into the sensor, the reflective skin conforms to the shape of the object's surface. Consequently, GelSight is a simple and effective system for controlling the material properties of the object, allowing for precise surface geometry capture of any material. We have built several different systems using GelSight sensors, including a real-time texture scanner, a multi-touch trackpad, a robotic fingertip, a portable texture scanner, and recently a microgeometry capture system capable of resolving geometry below 2 microns. In this talk, I will give an overview of GelSight and then describe how the sensor materials, illumination design, and capture techniques can be configured for microgeometry capture. I will show that the measured microgeometry can produce high levels of detail in rendering and describe a variety of applications where detailed microgeometry is important. Micah Kimo Johnson is a Research Scientist at MIT. His current research interests span computer vision and graphics, with an emphasis on image-based analysis of shape, illumination, color, and texture. In addition, he enjoys collaborating on interdisciplinary problems, such as art analysis, audio analysis, and music theory. He holds undergraduate degrees in Mathematics and Music Theory from the University of New Hampshire, an A.M. in Electro-Acoustic Music from Dartmouth College, and a Ph.D. in Computer Science from Dartmouth College.

1 1

J Song preFPO
by Melissa Lawson 14 Apr '11

14 Apr '11

Jimin Song will present her preFPO on Thursday April 21 at 10AM in Carl Icahn Lab 280 (note room!). The members of her committee are: Mona Singh, advisor; Olga Troyanskaya and Tom Funkhouser, readers; Bernard Chazelle and Andrea LaPaugh, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ------------------------------------------- Protein functioning and the role of cellular network topology Virtually all biological processes are accomplished via numerous specific interactions amongst various types of molecules. In the past decade, experimental and computational technologies have determined large numbers of interactions of various types, including those corresponding to direct physical binding, to regulatory relationships, and to more abstract linkages such as genetic interactions which indicate that two proteins participate in related biological processes. Analysis of the resulting interaction networks are a promising approach for expanding our understanding of cellular functioning, pathways and organization. In this work, I use high-throughput protein physical interactions to uncover hints about the overall functional organization of the cell, and to understand the role of network topology in this functioning. In the first part of my thesis, I study the problem of uncovering, from large-scale protein physical interaction data, protein complexes and "functional modules", so-called groups of proteins that work together to perform some larger biological process. I develop a framework to assess how well network clustering approaches perform in uncovering protein complexes and biological processes, and in predicting protein functions. From an application of this framework, I find that topological characteristics of networks are a significant factor in the accuracy trade-offs between local and global (i.e. clustering) approaches for uncovering cellular functioning. In the second part of my thesis, I analyze protein physical interaction networks in order to better characterize a protein's essentiality (i.e., the property of whether a protein is necessary for a cell to survive) and to understand the interplay between different protein complexes and biological processes. First, in agreement with previous studies, I find that proteins that are central in cellular networks tend to be essential more frequently. Second, I find essential proteins within complexes and processes are topologically more central within these subnetworks. Third, I infer significant cross-talk relationships between complexes and processes. This "module network," comprised of complexes or processes as nodes and cross-talk between them as edges, shows how complexes and processes are organized in a cell. Finally, I uncover that essential complexes and processes are topologically more central in the module network.

1 0

Q Zhu general exam
by Melissa Lawson 14 Apr '11

14 Apr '11

Qian Zhu will present his research seminar/general exam on Wednesday April 20 at 10AM in Room 402. The members of his committee are: Olga Troyanskaya (advisor), Moses Charikar, and Tom Funkhouser. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------------------ Abstract: The human gene expression data are growing at an amazingly fast pace. This large compendium represents a potential gold mine of biological knowledge for generating hypotheses about complex human diseases. Despite the rapid growth of data, we are still lagging behind in the development of analysis and search methods to examine the data effectively. To date, there is no search system that allows for the fast exploration of the entire human compendium, which has limited the ability of the biological researchers to examine the data totally and effectively. We propose an integrative search system that enables context-sensitive, query-driven search of genes and experiments in the human microarray compendium. The system not only searches for the expression of a set of query genes, but also has the ability to suggest, based on co-expression, other genes that might be functionally related to the query. With these genes, biologists can design further wet-lab experiments to discover novel biological relationships. My talk will consist of two parts. In the first part, I will describe two major challenges that we face in the large-scale search of the human compendium. The first challenge is the diversity of gene-expression across datasets: using co-expression map, I will show how datasets exhibit differential co-expression patterns for genes in the same pathway. The second challenge, the microarray platform gene-coverage variability, can create potential biases during the integration of signals across datasets. In the second part, I will describe our search algorithm that battles the above challenges to deliver accurate and context-relevant search results. I will show how much improvement we can gain from knowing where to search (i.e., where the good datasets are). Finally, I will describe our initial PageRank-like iterative search algorithm that is designed to improve search context and accuracy. Reading list: Book chapters: Chapters 3 (3.1 - 3.4), 4 from Statistical analysis of gene expression microarray data Terry Speed Chapman and Hall/CRC; 1 edition (March 26, 2003) Chapters 13, 14, 20 from Artificial Intelligence: A Modern Approach Stuart Russel, Peter Norvig Prentice Hall; 2nd edition (2003) Papers: Disease signatures are robust across tissues and experiments. Dudley JT, Tibshirani R, Deshpande T, Butte AJ. Mol Syst Biol. 2009;5:307. Ontology-driven indexing of public datasets for translational bioinformatics. Shah NH, Jonquet C, Chiang AP, Butte AJ, Chen R, Musen MA. BMC Bioinformatics. 2009 Feb 5;10 Suppl 2:S1. Systematic bioinformatic analysis of expression levels of 17,330 human genes across 9,783 samples from 175 types of healthy and pathological tissues. Kilpinen S, Autio R, Ojala K, Iljin K, Bucher E, Sara H, Pisto T, Saarela M, Skotheim RI, Björkman M, Mpindi JP, Haapa-Paananen S, Vainio P, Edgren H, Wolf M, Astola J, Nees M, Hautaniemi S, Kallioniemi O. Genome Biol. 2008;9(9):R139. Exploring the functional landscape of gene expression: directed search of large microarray compendia. Hibbs MA, Hess DC, Myers CL, Huttenhower C, Li K, Troyanskaya OG. Bioinformatics. 2007 Oct 15;23(20):2692-9. Cross-platform analysis of cancer microarray data improves gene expression based classification of phenotypes. Warnat P, Eils R, Brors B. BMC Bioinformatics. 2005 Nov 4;6:265. Putting microarrays in a context: integrated analysis of diverse biological data. Troyanskaya OG. Brief Bioinform. 2005 Mar;6(1):34-43. Large-scale meta-analysis of cancer microarray data identifies common transcriptional profiles of neoplastic transformation and progression. Rhodes DR, Yu J, Shanker K, Deshpande N, Varambally R, Ghosh D, Barrette T, Pandey A, Chinnaiyan AM. Proc Natl Acad Sci U S A. 2004 Jun 22;101(25):9309-14. Topic-sensitive PageRank: a context-sensitive ranking algorithm for web search. Haveliwala TH. IEEE Transactions on Knowledge and Data Engineering. 2003 Jul/Aug; 4 (15): 784-796. Transitive functional annotation by shortest-path analysis of gene expression data. Zhou X, Kao MC, Wong WH. Proc Natl Acad Sci U S A. 2002 Oct 1;99(20):12783-8.

1 0

Colloquium Speaker, Percy Liang, Wed. April 6
by Nicole E. Wagenblast 05 Apr '11

05 Apr '11

Deep Semantics from Shallow Supervision Percy Liang, UC Berkeley Wednesday April 6, 4:30pm Computer Science 105 What is the total population of the ten largest capitals in the US? Building a system to answer free-form questions such as this requires modeling the deep semantics of language. But to develop practical, scalable systems, we want to avoid the costly manual annotation of these deep semantic structures and instead learn from just surface-level supervision, e.g., question/answer pairs. To this end, we develop a new tree-based semantic representation which has favorable linguistic and computational properties, along with an algorithm that induces this hidden representation. Using our approach, we obtain significantly higher accuracy on the task of question answering compared to existing state-of-the-art methods, despite using less supervision. Percy Liang obtained a B.S. (2004) and an M.S. (2005) from MIT and is now completing his Ph.D. at UC Berkeley with Michael Jordan and Dan Klein. The general theme of his research, which spans machine learning and natural language processing, is learning richly-structured statistical models from limited supervision. He has won a best student paper at the International Conference on Machine Learning in 2008, received the NSF, GAANN, and NDSEG fellowships, and is also a 2010 Siebel Scholar.

1 1

J Calandrino preFPO
by Melissa Lawson 04 Apr '11

04 Apr '11

Joe Calandrino will present his preFPO on Friday April 8 at 4PM in Room 402. The members of his committee are: Ed Felten, advisor; Andrew Appel and Jen Rexford, readers; Brian Kernighan and David Walker, nonreaders. Everyone is invited to attend his talk. His abstract follow below. ------------------------------- Title: Control of Sensitive Data in Systems with Novel Functionality Abstract: Advances in computer science have enabled analysis of data in ways previously unthinkable. This has led to powerful new uses of data, often with positive results. For systems utilizing sensitive data, however, an adversary's ability to scrutinize revealed output for sensitive details has also increased. The threat is particularly great for systems with novel functionality. Novel uses of data are often accompanied by implicit assumptions. As a result, exposure of seemingly innocuous information may reveal underlying sensitive data in unexpected new ways. We study this issue in the context of three diverse cases. The first case that we consider is fill-in-the-bubble forms, which are used in a variety of situations where protection or confirmation of identity is critical. Although bubble-form surveys, elections ballots, or standardized test forms are often treated as anonymous, we demonstrate that individuals complete bubbles in a distinctive manner, allowing de-anonymization. Second, we consider collaborative filtering recommender systems, which often use sensitive transactions to infer relationships between items. We show that an attacker can exploit dynamic changes in recommendations to infer individual underlying transactions. Finally, we explore the use of machines and algorithms in election auditing to ensure an accurate election outcome efficiently without compromising ballot secrecy or trusting voting machines. Each case employs sensitive data in unique ways, yielding unique vectors for data leakage. For systems utilizing sensitive data in novel ways, developers must carefully assess the relationship between that data and the system's output. Undesirable inferences frequently stem from unstated or untested assumptions that no meaningful link exists. Careful evaluation can make these assumptions explicit and address them before releasing data to potential adversaries.

1 0

Colloquium Speaker Isil Dillig Tuesday April 5
by Nicole E. Wagenblast 04 Apr '11

04 Apr '11

Precise and Fully-Automatic Verification of Container-Manipulating Programs Isil Dillig, Stanford University Tuesday April 5, 4:30pm Computer Science 105 One of the key challenges in automated software verification is obtaining a conservative, yet sufficiently precise understanding of the contents of data structures in the heap. A particularly important and widely-used class of heap data structures is containers, which support operations such as inserting, retrieving, removing, and iterating over elements. Examples of containers include arrays, lists, vectors, sets, maps, stacks, queues, etc. In this talk, I will describe a sound, precise, scalable, and fully-automatic static analysis technique for reasoning about the contents of container data structures. This technique is capable of tracking position-value and key-value correlations, supports reasoning about arbitrary nestings of these data structures, and integrates container reasoning directly into a heap analysis, allowing, for the first time, the verification of complex programs that manipulate heap objects through container data structures. More specifically, I will describe a symbolic heap abstraction that augments a graph representation of the heap with logical formulas and that reduces some of the difficulty of heap reasoning to standard logic operations, such as existential quantifier elimination and satisfiability. I will present experimental results demonstrating that our technique is very useful for verifying memory safety in complex heap- and container-manipulating C and C++ programs that use arrays and other container data structures from the STL and QT libraries. Isil Dillig is a PhD candidate at the Computer Science Department at Stanford University, advised by Prof. Alex Aiken. Her research interests include software verification, static analysis, and constraint solving. Isil received her undergraduate degree from Stanford in 2006, with a major in computer science with honors and distinction. She is the recipient of Frederick Emmons Terman Engineering Scholastic Award at Stanford, as well as the recipient of Forbes School of Engineering and Stanford Graduate Fellowships.

1 1

Colloquium Speaker, Thomas Dillig, Monday April 4
by Nicole E. Wagenblast 01 Apr '11

01 Apr '11

Program Paths Simplified: Scalable Path-Sensitive Analysis without Heuristics Thomas Dillig, Stanford University Monday, April 4, 4:30pm Computer Science 105 A path-sensitive static analysis considers each possible execution path through a program separately, potentially yielding much more precise results than an analysis that makes fewer distinctions among paths. While precise path-sensitive reasoning is known to be necessary to prove many interesting facts about programs, fully path-sensitive analyses have not scaled well because standard representations of program paths quickly grow out of control. In this talk, I will describe two techniques that allow path-sensitive program analyses to scale. I will first introduce on-line constraint simplification, which eliminates redundant subparts of logical formulas used to distinguish execution paths. In practice, the formulas used to describe program paths are highly redundant; thus, techniques for keeping path formulas concise can have a dramatic impact on analysis scalability. A second, complementary technique reduces formula size even further: Because static analyses are typically only interested in answering may (i.e., satisfiability) and must (i.e., validity) queries, I will show how to extract from the original path formulas a pair of satisfiabilty- and validity-preserving formulas that contain many fewer variables and that are as good as the original path formula for answering may and must queries about the program. I will demonstrate that these techniques allow a fully path-sensitive analysis to scale to very large, multi-million line programs for the first time. Thomas Dillig is a PhD candidate at Stanford University. Thomas obtained his undergraduate degree in computer science from Stanford University in 2006 with distinction and honors. His main research interests are program verification, programming languages and constraint solving.

1 0

Colloquium Speaker, Percy Liang, Wed. April 6
by Nicole E. Wagenblast 31 Mar '11

31 Mar '11

Deep Semantics from Shallow Supervision Percy Liang, UC Berkeley Wednesday, April 6, 4:30pm Computer Science 105 What is the total population of the ten largest capitals in the US? Building a system to answer free-form questions such as this requires modeling the deep semantics of language. But to develop practical, scalable systems, we want to avoid the costly manual annotation of these deep semantic structures and instead learn from just surface-level supervision, e.g., question/answer pairs. To this end, we develop a new tree-based semantic representation which has favorable linguistic and computational properties, along with an algorithm that induces this hidden representation. Using our approach, we obtain significantly higher accuracy on the task of question answering compared to existing state-of-the-art methods, despite using less supervision. Percy Liang obtained a B.S. (2004) and an M.S. (2005) from MIT and is now completing his Ph.D. at UC Berkeley with Michael Jordan and Dan Klein. The general theme of his research, which spans machine learning and natural language processing, is learning richly-structured statistical models from limited supervision. He has won a best student paper at the International Conference on Machine Learning in 2008, received the NSF, GAANN, and NDSEG fellowships, and is also a 2010 Siebel Scholar.

1 0

Q Xi preFPO
by Melissa Lawson 31 Mar '11

31 Mar '11

Qian Xi will present her preFPO on Tuesday April 5 at 1PM in Room 301 (note room). The members of her committee are David Walker, advisor; Andrew Appel and Yitzhak Mandelbaum (AT&T), readers; Brian Kernighan and Andrea LaPaugh, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. Title: Generation of Data Processing Tools for Context-free and Context Dependent Grammars Abstract: An ad hoc data format is any nonstandard, semi-structured data format for which robust data processing tools are not easily available. Ad hoc data exists in many domains, but processing it is challenging. The goal of this research is to find a generic, reliable and efficient method to extract the structural information from ad hoc data files, which is the key step to complete before generating auxiliary data processing tools, such as parsers, pretty printers, query engines, XML converters etc. In this dissertation, we first focus on the context-free grammars in ad hoc data sources. We design a markup language called Anne that programmers can use to annotate raw text with a set of grammatical directives. The Anne system then uses a combination of user annotations and the raw data itself to extract a context-free grammar from which the system further generates a PADS description, a Yakker description, and an XML representation of the data. To thoroughly understand Anne, we formalize a semantic theory to capture the core features of the language. This semantic theory includes the editing process, which translates a raw, unannotated document into an annotated one, and the grammar extraction process, which generates a context-free grammar from the annotated document. When reasoning about the relationship between the raw data and the generated grammar, we also find an interesting connection to the field of classic relevance logic. This relevance analysis allows us to prove important theorems concerning the expressiveness of the language. We implement the system and conduct two major experiments measuring the amount of effort needed to annotate documents and the quality of the generated grammars. Then we extend the coverage of Anne to context dependent grammars by adding new features in the syntax and semantic rules of the formalization, including variable bindings, data-dependent constraint, and transformations. We demonstrate the relevance analysis is a robust theory by proving all the principle theorems still hold after this extension. Our experience of using dependent parser generator shows that arbitrary dependent grammars can be costly to parse, and thus we are motivated to build more efficient parsers. We apply an analysis of dependent grammars to find particular subparts that do not rely on general dependent parsing and can therefore use conventional optimization techniques. We give formal definitions of the analysis and use it to guide implementation. The results of the implementation demonstrate that the efficiency of parsing is improved by the analysis.

1 0