April 2008 - talks - lists.cs.princeton.edu

C Barnes general exam
by Melissa M Lawson 29 Apr '08

29 Apr '08

Connelly Barnes will present his research seminar/general exam on Tuesday May 6 at 3PM in Room 402. The members of his committee are: Adam Finkelstein (advisor), Szymon Rusinkiewicz, and Perry Cook. 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: We present a video-based interface that allows users of all skill levels to quickly create cutout-style animations by performing the character motions. The puppeteer first creates a cast of physical puppets using paper, markers and scissors. He then physically moves these puppets to tell a story. Using an inexpensive overhead camera our system tracks the motions of the puppets and renders them on a new background while removing the puppeteer's hands. Our system runs in real-time (at 30 fps) so that the puppeteer and the audience can immediately see the animation that is created. Moreover, our system supports a variety of constraints and effects including articulated characters, multi-track animation, scene changes, camera controls, 2.5D environments, shadows, and animations cycles. We demonstrate that even first-time users, including an eleven-year-old, can use our system to quickly turn a story idea into an animation. Reading list, books: Trucco and Verri, Introductory Techniques for 3-D Computer Vision Reading list, papers: Igarashi, T, Moscovich, T, Hughes, J. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. (Proc. SIGGRAPH), 1134-1141. Lowe, D. 1999. Object recognition from local scale-invariant features. International Conference on Computer Vision, 1150-1157. Thorne, M, Burke, D, Van de Panne, M. 2004. Motion doodles: an interface for sketching character motion. SIGGRAPH '04: ACM SIGGRAPH 2004 Papers, ACM Press, New York, NY, USA, 424-431. Tomasi, C, Kanade, T. 1991. Detection and tracking of point features. Technical Report CMU-CS-91-132, Carnegie Mellon University, Pittsburgh, PA, USA. David, J, Agrawala, M, Chuang, E, Popovic, Z, Salesin, D. 2003. A sketching interface for articulated figure animation. Proc. 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, Aire-la-Ville, Switzerland, 320-328. Dontcheva, M, Yngve, G, Popovic, Z. 2003. Layered acting for character animation. ACM SIGGRAPH 2003 Papers, ACM Press, New York, NY, USA, 409-416. Winnemoller, H, Olsen, S, Gooch, B. 2006. Realtime video abstraction. ACM Transactions on Graphics (TOG) 25, 3, 1221-1226. Agarwala, A, Hertzmann, A, Salesin, D, Seitz, S. 2004. Keyframe-based tracking for rotoscoping and animation. SIGGRAPH '04: ACM SIGGRAPH 2004 Papers, ACM Press, New York, NY, USA, 584-591. Ishii, H, Ullmer, B. 1997. Tangible bits: towards seamless interfaces between people, bits and atoms. Proc. SIGCHI conference on Human factors in computing systems, 234-241. Knep, B, Hayes, C, Sayre, R, Williams, T. 1995. Dinosaur input device. Proc. SIGCHI conference on Human factors in computing systems, 304-309.

1 0

A Misra preFPO
by Melissa M Lawson 29 Apr '08

29 Apr '08

Ananya Misra will present her preFPO on Tuesday May 6 at 1PM in Room 302 (note room). The members of her committee are: Perry Cook, advisor; Georg Essl and Dan Trueman, readers; Ken Steiglitz and Szymon Rusinkiewicz, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. Abstract: TAPESTREA is a sound design and composition framework that facilitates the creation of new sound from existing digital audio recordings, through interactive analysis, transformation and re-synthesis. During analysis, sinusoidal modeling and transient detection techniques are used to parametrically extract desired sound templates of different types: sinusoidal events, transient events, and stochastic background. Each extracted template is transformed and synthesized independently using an appropriate technique, such as sinusoidal re-synthesis or wavelet tree learning. This allows specialized transformations on each template based on its type; sinusoidal templates undergo real-time, large-scale time and frequency transformations, while background is generated parametrically from extracted samples. The user interacts with TAPESTREA via a set of graphical interfaces. Synthesis is further controlled through ChucK scripts, which allow simultaneous, precise manipulation of many parameters. They also allow control via external input devices and user-defined GUI elements. These combined techniques form a workbench for completely transforming a sound scene, dynamically generating soundscapes, or creating musical tapestries by weaving together transformed elements from different recordings. Thus, TAPESTREA introduces a new paradigm for composition, sound design, and other sonic sculpting tasks. Work on further improving the system includes user studies to compare alternative algorithms for generating stochastic background noise.

1 0

R Manokaran general exam
by Melissa M Lawson 29 Apr '08

29 Apr '08

Rajsekar Manokaran will present his research seminar/general exam on Monday May 5 at 2PM in Room 402. The members of his committee are: Sanjeev Arora (advisor), Moses Charikar, and Boaz Barak. Everyone is welcome 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 appear below. Abstract -------- Mathematical relaxations are one of the most powerful tools used in designing approximation algorithms for hard combinatorial optimization problems. For example, linear programming relaxations have provided the best approximation algorithms known for a huge number of optimization problems. More recently, for some optimization problems, semidefinite relaxations have been used to obtain breakthrough improvements in the approximation factor. This work investigates the limits on approximations achieved by mathematical relaxations of combinatorial optimization problems and their relation to the computation hardness of approximating them. For a small yet quite general set of problems, a direct way to convert integrality gaps for a linear programming relaxation of the problem into a computational hardness result under a certain conjecture is shown. This problem, known as metric labeling is a generalization of classification problems with pairwise constraints. In this work, it is shown that a certain linear programming relaxation gives the best approximation one can expect, assuming the unique games conjecture. Continuing in the same theme, a similar computational hardness result is shown for the maximum acyclic subgraph problem. Here, a trivial algorithm obtains a half approximation and obtaining a better approximation algorithm has been an open problem for quite some time. Assuming the UG conjecture, this work shows that it is computationally hard to approximate the maximum acyclic subgraph problem by a better factor is hard. This result also, unconditionally, rules out a simple semi-definite programming approach to obtain a better approximation. Reading List ------------ 1. Complexity Theory: A Modern Approach by Sanjeev Arora and Boaz Barak Chapters 1-8, 16-19. 2. Approximation Algorithms by Vijay Vazirani Chapters 1-4, 12-21. 3. Expander Flows, Geometric Embeddings, and Graph Partitionings by Sanjeev Arora, Satish Rao, and Umesh Vazirani ACM Symposium on Theory of Computing, 2004. 4. A tight bound on approximating arbitrary metrics by tree metrics by Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar ACM Symposium on Theory of Computing, 2003 5. Some Optimal Inapproximability Results by Johan Hastad STOC 1997. 6. Proving integrality gaps without knowing the linear program. by Sanjeev Arora, Bela Bollobas and Laszlo Lovasz. Proc. IEEE Foundations of Computer Science, 2002. 7. Local Global Tradeoffs in Metric Embeddings, by Moses Charikar, Konstantin Makarychev, Yury Makarychev, FOCS 2007, pp. 713-723. 8. On the power of unique 2-prover 1-round games by Subhash Khot STOC '02. 9. Optimal inapproximability results for max-cut and other 2-variable csps? by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. FOCS '04. 10. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into $L_1$. by Subhash Khot and Nisheeth Vishnoi. FOCS '05. 11. Noise stability of functions with low influences: Invariance and optimality. by Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. FOCS '05. 12. Vertex cover might be hard to approximate to within 2-$\epsilon$. by Subhash Khot and Oded Regev. J. Comput. Syst. Sci. 13. Near-Optimal Algorithms for Unique Games, by Moses Charikar, Konstantin Makarychev, Yury Makarychev, STOC 2006, pp. 205-214. 14. Approximation algorithms for the metric labeling problem via a new linear programming formulation. Chandra Chekuri, Sanjeev Khanna, Joseph (Seffi) Naor, and Leonid Zosin. SIAM J. Disc. Math. 15. On the advantage over random for maximum acyclic subgraph. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. FOCS 2007, pp. 625-633.

1 0

R Pang FPO
by Melissa M Lawson 28 Apr '08

28 Apr '08

Ruoming Pang will present his FPO on Monday May 5 at 10AM in Room 402. The members of his committee are: Larry Peterson, advisor; Jen Rexford and Vern Paxson (ISCI), readers; Vivek Pai and Brian Kernighan, nonreaders. A copy of his thesis, "Towards Understanding Application Semantics of Network Traffic", is on display in Room 310. Everyone is invited to attend his talk.

1 0

4:30pm Tue Apr 29 talk by Robert Nowak on network inference
by Jennifer Rexford 25 Apr '08

25 Apr '08

*Speaker: *Robert Nowak, Professor of Engineering at the University of Wisconsin-Madison *Date: *Tuesday, April 29th *Time: *4:30pm *Room: *B205 ~ Equad *Title: *Network Inference from Co-Occurrences *Abstract: *The discovery of networks is a fundamental problem arising in numerous fields of science and engineering, including communication systems, biology, sociology, and neuroscience. Unfortunately, it is often difficult to obtain data that directly reveal network structure, and so one must infer a network from incomplete data. This paper considers inferring network structure and transmission pathways from ``co-occurrence'' data; observations that identify which network components (e.g., routers, proteins) carry each transmission but do not indicate the order in which they handle the transmission. Without order information, the number of networks that are consistent with the data grows exponentially with the size of the network. Yet, the basic engineering/ evolutionary principles underlying most networks strongly suggest that not all data-consistent networks are equally likely. In particular, network components that co-occur in many observations are probably closely connected. With this in mind, we model the co-occurrence observations as independent realizations of a random walk on the network graph, subjected to random permutations which account for the lack of order information. The network can be estimated using this model and the Maximum Likelihood (ML) criterion. The computational complexity of direct ML estimation is combinatorial in the size of the network, and so we derive a more efficient approach using an Expectation-Maximization (EM) algorithm. The EM algorithm complexity is combinatorial in the length of the transmission pathways, rather than the size of the entire network. This is a significant improvement, but the computational cost of the EM algorithm is still prohibitive for large networks. For large-scale network inference, we propose a polynomial-time Monte Carlo version of the EM algorithm which is guaranteed to converge with high probability. Applications arising in telecommunications, natural language processing, and systems biology will be discussed. * * *Bio: *Robert Nowak received the B.S. (with highest distinction), M.S., and Ph.D. degrees in electrical engineering from the University of Wisconsin-Madison in 1990, 1992, and 1995, respectively. He was a Postdoctoral Fellow at Rice University in 1995-1996, an Assistant Professor at Michigan State University from 1996-1999, held Assistant and Associate Professor positions at Rice University from 1999-2003, and was a Visiting Professor at INRIA in 2001. Dr. Nowak is now the McFarland-Bascom Professor of Engineering at the University of Wisconsin-Madison. He has served as an Associate Editor for the IEEE Transactions on Image Processing, and is currently an Associate Editor for the ACM Transactions on Sensor Networks and the Secretary of the SIAM Activity Group on Imaging Science. He has also served as a Technical Program Chair for the IEEE Statistical Signal Processing Workshop and the IEEE/ACM International Symposium on Information Processing in Sensor Networks. Dr. Nowak received the General Electric Genius of Invention Award in 1993, the National Science Foundation CAREER Award in 1997, the Army Research Office Young Investigator Program Award in 1999, the Office of Naval Research Young Investigator Program Award in 2000, and IEEE Signal Processing Society Young Author Best Paper Award in 2000. His research interests include statistical signal processing, machine learning, imaging and network science, and applications in communications, bio/medical imaging, and systems biology.

1 0

B Brown FPO
by Melissa M Lawson 24 Apr '08

24 Apr '08

Benedict Brown will present his FPO on Thursday May 1 at 10:30AM in Room 402. The members of his committee are; Szymon Rusinkiewicz, advisor; David Dobkin and Tom Funkhouser, readers; Adam Finkelstein and Ken Steiglitz, nonreaders. A copy of his thesis, "Registration and Matching of Large Geometric Datasets for Cultural Heritage Applications" is on display in Room 310. Everyone is invited to attend his talk.

1 0

1-2pm Wed May 7 talk on learning structured bayesian networks in room 302
by Jennifer Rexford 23 Apr '08

23 Apr '08

Title: *Learning Structured Bayesian Networks: Combining Abstraction Hierarchies and Tree-Structured Conditional Probability Tables Speaker: **Marie desJardins*, University of Maryland Date/time: 1-2pm Wed May 7 Location: room 302 in the CS building Abstract: In this talk, I will describe our research on incorporating background knowledge in the form of feature hierarchies during Bayesian network learning. Feature hierarchies enable the learning system to aggregate categorical variables in meaningful ways, thus enabling an appropriate "discretization" for a categorical variable. In addition, by choosing the appropriate level of abstraction for the parent of a node, we also support compact representations for the local probability models in the network. We combine this notion of selecting an appropriate abstraction with context-specific independence representations, which capture local ndependence relationships among the random variables in the Bayesian network. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. I will describe our primary contribution, the Tree-Abstraction-Based Search (TABS) algorithm, which learns a data distribution by inducing the graph structure and parameters of a Bayesian network from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. In order to construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. Empirical results in several benchmark domains show that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies. BIOGRAPHY Dr. Marie desJardins is an associate professor in the Department of Computer Science and Electrical Engineering at the University of Maryland, Baltimore County. Her research is in artificial intelligence, focusing on the areas of machine learning, multi-agent systems, planning, interactive AI techniques, information management, reasoning with uncertainty, and decision theory. Dr. desJardins can be contacted at the Dept. of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore MD 21250, mariedj(a)cs.umbc.edu,(410) 455-3967.

1 0

Refreshments
by Ginny Hogan 23 Apr '08

23 Apr '08

Are now available in the tea room - Followed by Umesh Vazirani's talk At 4:30 -

1 0

Talk today - 4:30 - COS 105
by Ginny Hogan 23 Apr '08

23 Apr '08

Umesh Vazirani, UC Berkeley, will present his talk "The Truth about Quantum Computers", at 4:30pm today COS 105 - Tea will be at 3:30pm

1 0

Zhiyan Liu FPO
by Melissa M Lawson 21 Apr '08

21 Apr '08

Zhiyan Liu will present her FPO on Friday April 25 at 1:30PM in Room 302 (note room). The members of her committee are: Kai Li, advisor; Adam Finkelstein and Olga Troyanskaya, readers; Tom Funkhouser and Szymon Rusinkiewicz, nonreaders. A copy of her thesis, "Scalable Isosurface Visualization", is on display in Room 310. Everyone is invited to attend her talk.

1 0