- talks - lists.cs.princeton.edu

Connelly Barnes FPO
by Melissa Lawson 26 Apr '11

26 Apr '11

Connelly Barnes will present his FPO on Tuesday May 3 at 12:30PM in Room 402. The members of his committee are; Adam Finkelstein, advisor; Szymon Rusinkiewicz and Dan Goldman (Adobe), readers; Tom Funkhouser and Bob Sedgewick, nonreaders. A copy of his thesis, "PatchMatch: A Fast Randomized Matching Algorithm with Application to Image and Video", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Corey Toler-Franklin FPO
by Melissa Lawson 26 Apr '11

26 Apr '11

Corey Toler-Franklin will present her FPO on Tuesday May 3 at 10AM in Room 402. The members of her committee are: Szymon Rusinkiewicz, advisor; Tom Funkhouser and Holly Rushmeier (Yale), readers; Adam Finkelstein and David Blei, nonreaders. A copy of her thesis, "Matching, Archiving and Visualizing Cultural Heritage Artifacts Using Multi-Channel Images", is on display in Room 310. Everyone is invited to attend her talk.

1 0

R Harrison MSE thesis talk
by Melissa Lawson 25 Apr '11

25 Apr '11

Rob Harrison will present his MSE thesis talk on Friday April 29 at 10AM in Room 402. Jen Rexford is his advisor, and David Walker is his reader. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------- ABSTRACT: Network administrators must configure network devices to simultaneously provide several interrelated services such as routing, load balancing, traffic monitoring, and access control. Unfortunately, most interfaces for programming networks are defined at the low level of abstraction supported by the underlying hardware, leading to complicated programs with subtle bugs. We present Frenetic, a high-level language for programming networks that enables writing programs in a declarative and compositional style, with a simple ``program like you see every packet'' abstraction. Frenetic consists of a rich network query language, a network management library, and a run-time system. The run-time system efficiently manages the low-level details of installing, uninstalling, and querying the low-level packet-processing rules on physical switches. We describe the design of the Frenetic language and run-time system, an implementation on top of the OpenFlow architecture, experiments and example programs that validate our design choices.

1 0

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