- talks - lists.cs.princeton.edu

Chris Bregler Talk on Monday at noon in CS 402
by Thomas Funkhouser 25 Apr '11

25 Apr '11

**There will be a talk of broad interest by Chris Bregler from NYU in the PIXL lunch talk series at noon on Monday in CS 402. All are welcome. ** // *From Eye-Balls to Ball-Games: Next-Gen Motion Capture for Science and Entertainment* /Chris Bregler, NYU / *Abstract* This talk will cover several research projects centered around the use of vision and motion capture for animation, recognition, and gaming. This includes human movements as diverse as subtle eye-blinks, lip-motions, spine-deformations, human walks and dances, politicians, base-ball pitchers, and the production of the largest motion capture game to date. The technical content of the talk focuses on the trade-off between data-driven models of human motion vs. analytically derived and perceptually driven models using dancers, animators, linguists, and other domain experts. This is demonstrated by sub-pixel tracking in Hollywood productions, reading the body-language of public figures, visualizing the pitches of NY Yankees Mariano Rivera, and the making of crowd mocap games in various cultures. ------------------------------------------------------------------------

1 1

C Beck general exam
by Melissa Lawson 20 Apr '11

20 Apr '11

Chris Beck will present his research seminar/general exam on Monday April 25 at 11AM in room 401 (note room). The members of his committee are: Sanjeev Arora (advisor), Bernard Chazelle, and Moses Charikar. 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: For modern SAT solvers based on DPLL with clause learning, the two major bottlenecks are the time and memory used by the algorithm. There is a well known correspondence between these algorithms and the Resolution proof system, in which these resources correspond to the length and space of proofs. Lately there has been great theoretical interest in understanding the interplay of these two resources, and in obtaining Time Space Tradeoff results. In 2010, Eli Ben-Sasson and Jakob Nordström demonstrated formulae which have linear sized proofs using linear space, but which require exponentially large proofs when the space is constrained to be n / log n. It remains a major open question to obtain similar lower bounds against time but with a more mild space assumption, since in practice SAT solvers generally are not used on instances so large that they exceed the available memory. We obtain strong tradeoff results for Regular Resolution, a restricted form of General Resolution. For each k, we can find formulae of length n which may be proved in time n^(k+1) with space n^k, but such that with space at most n^(k - epsilon), superpolynomial time is necessary in any proof. Our analysis relies on a random adversary related to those used in Prover Adversary games, normally thought to be relevant only to very weak proof systems. This innovation permits a comparatively simple lower bound argument, avoiding completely the use of random restrictions. Reading List: Resolution (1): Eli Ben-Sasson, Avi Wigderson <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/w/Wigderson:Avi…> : Short proofs are narrow - resolution made simple. J. ACM 48 <http://www.informatik.uni-trier.de/%7Eley/db/journals/jacm/jacm48.html#Ben-…> (2): 149-169 (2001) Resolution Space (3): Michael Alekhnovich <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/a/Alekhnovich:M…> , Eli Ben-Sasson, Alexander A. Razborov <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/r/Razborov:Alex…> , Avi Wigderson <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/w/Wigderson:Avi…> : Space Complexity in Propositional Calculus. SIAM J. Comput. 31 <http://www.informatik.uni-trier.de/%7Eley/db/journals/siamcomp/siamcomp31.h… hBRW02> (4): 1184-1211 (2002) Albert Atserias, Víctor Dalmau <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/d/Dalmau:V=iacu…> : A combinatorial characterization of resolution width. J. Comput. Syst. Sci. 74 <http://www.informatik.uni-trier.de/%7Eley/db/journals/jcss/jcss74.html#Atse…> (3): 323-334 (2008) Eli Ben-Sasson, Jakob Nordström <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/n/Nordstr=ouml=…> : Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs. Electronic Colloquium on Computational Complexity (ECCC) 16 <http://www.informatik.uni-trier.de/%7Eley/db/journals/eccc/eccc16.html#Ben-…> : 34 (2009) Polynomial Calculus (4): <http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-SassonI99.xml> Image removed by sender. bibliographical record in XMLEli Ben-Sasson, Russell Impagliazzo <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/i/Impagliazzo:R…> : Random CNF's are Hard for the Polynomial Calculus. FOCS 1999 <http://www.informatik.uni-trier.de/%7Eley/db/conf/focs/focs99.html#Ben-Sass…> : 415-421 Samuel R. Buss <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/b/Buss:Samuel_R…> , Dima Grigoriev <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/g/Grigoriev:Dim…> , Russell Impagliazzo, Toniann Pitassi <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/p/Pitassi:Tonia…> : Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. J. Comput. Syst. Sci. 62 <http://www.informatik.uni-trier.de/%7Eley/db/journals/jcss/jcss62.html#Buss…> (2): 267-289 (2001) Russell Impagliazzo, Pavel Pudlák <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/p/Pudl=aacute=k…> , Jiri Sgall <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/s/Sgall:Jiri.ht…> : Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. Computational Complexity 8 <http://www.informatik.uni-trier.de/%7Eley/db/journals/cc/cc8.html#Impagliaz…> (2): 127-144 (1999) Matthew Clegg <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/c/Clegg:Matthew…> , Jeff Edmonds <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/e/Edmonds:Jeff.…> , Russell Impagliazzo: Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. STOC 1996 <http://www.informatik.uni-trier.de/%7Eley/db/conf/stoc/stoc1996.html#CleggE…> : 174-183 AC^0-Frege (2): Paul Beame and Søren Riis. More on the relative strength of counting principles <http://www.cs.washington.edu/homes/beame/papers/riis.ps> . In Paul W. Beame and Samuel R. Buss, editors, Proof Complexity and Feasible Arithmetics, volume 39 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 13-35. American Mathematical Society, 1998. Also related: Paul Beame. A switching lemma primer <http://www.cs.washington.edu/homes/beame/papers/primer.ps> . Technical Report UW-CSE-95-07-01, Department of Computer Science and Engineering, University of Washington, November 1994. SAT solvers & Model Checking (1): Lintao Zhang, Conor F. Madigan, Matthew H. Moskewicz, Sharad Malik, "Efficient Conflict Driven Learning in a Boolean Satisfiability Solver," iccad, pp.279, 2001 International Conference on Computer-Aided Design (ICCAD '01), 2001 Verification/Model Checking(1): <http://scholar.google.com/scholar?q=%22Bounded+Model+Checking+Using+Satisfi… g.%22> Image removed by sender. Google scholar <http://dblp.uni-trier.de/rec/bibtex/journals/fmsd/ClarkeBRZ01> Image removed by sender. BibTeX <http://dblp.uni-trier.de/rec/bibtex/journals/fmsd/ClarkeBRZ01.xml> Image removed by sender. bibliographical record in XMLEdmund M. Clarke <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/c/Clarke:Edmund…> , Armin Biere, Richard Raimi <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/r/Raimi:Richard…> , Yunshan Zhu <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/z/Zhu:Yunshan.h…> : Bounded Model Checking Using Satisfiability Solving. Formal Methods in System Design 19 <http://www.informatik.uni-trier.de/%7Eley/db/journals/fmsd/fmsd19.html#Clar…> (1): 7-34 (2001)

1 0

R Wang MSE thesis talk
by Melissa Lawson 19 Apr '11

19 Apr '11

Richard Wang will present his master's thesis talk on Friday April 22 at 10:30AM in Room 301. His advisor is Jen Rexford. Everyone is invited to attend his talk. His abstract follows below. -------------------- abstract: Today's data centers host online services on multiple servers, with a front-end load balancer directing each client request to a particular replica. Dedicated load balancers are expensive and quickly become a single point of failure and congestion. The OpenFlow standard enables an alternative approach where the commodity network switches divide traffic over the server replicas, based on packet-handling rules installed by a separate controller. However, the simple approach of installing a separate rule for each client connection (or "microflow") leads to a huge number of rules in the switches and a heavy load on the controller. We argue that the controller should exploit switch support for wildcard rules for a more scalable solution that directs large aggregates of client traffic to server replicas. We present algorithms that compute concise wildcard rules that achieve a target distribution of the traffic, and automatically adjust to changes in load-balancing policies without disrupting existing connections. We implement these algorithms on top of the NOX OpenFlow controller, evaluate their effectiveness, and propose several avenues for further research.

1 0

M Arye MSE thesis talk
by Melissa Lawson 19 Apr '11

19 Apr '11

Matvey Arye will present his master's thesis talk on Friday April 22 at 10AM in Room 301. His advisor is Mike Freedman. Everyone is welcome to attend his talk. His abstract follows below. ------------------------------- Abstract: Currently, the Internet does not support device mobility natively. If a device moves across layer-2 domains, there is no way to preserve connectivity for ongoing connections. Similarly, there is no support for using multiple points of attachment (e.g. WiFi and 3G) concurrently on a single connection. This talk introduces FlexMove, an in-band, formally verified, protocol that supports device mobility and introduces a flow abstraction that enables connections to use multiple points of attachment. This talk will also describe the problems encountered and lessons learned while modeling and verifying this protocol using a tool called SPIN.

1 0

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