- talks - lists.cs.princeton.edu

Y Pritykin generals
by Melissa Lawson 14 Oct '10

14 Oct '10

Yury Pritykin will present his research seminar/general exam on Wednesday October 20 at 10AM in Room 402. The members of his committee are: Mona Singh, advisor, Tom Funkhouser, 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 ======== Biological networks at different organization levels have proved useful for understanding of basic biological principles. Two complementary types of networks can be considered on a cellular level. One is the network of interactions between genes and proteins in a cell. It can be represented as a graph with directed and undirected edges of different types. Various methods have been used to study these kinds of networks in order to improve our understanding of functioning of cells and organisms. Another technique of expression and protein quantitative trait loci (eQTLs and pQTLs) aims to detect associations of locations in the genome with variation in a quantitative trait, in this case gene activity measured as transcript expression or protein abundance. The result of such analysis can be represented as a bipartite graph with linkages between genetic loci and genes or proteins. This talk will show advantage of mutual analysis of the above two types of networks. As an example, we show that using eQTL linkage information integrated with interaction information can help to infer more pQTLs linkages than the standard approach. Reading list ============ D. Mount. Bioinformatics: Sequence and Genome Analysis. 2nd Edition, Cold Spring Harbor Laboratory Press, 2004. Chapters 1-7, 10. T. Ideker, O. Ozier, B. Schwikowski, A. F. Siegel. Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics, 18 Suppl 1, 2002, p. S233-40. V. Spirin, L. Mirny. Protein complexes and functional modules in molecular networks. Proceedings of the National Academy of Sciences of the United States of America. 100, 2003, pp. 12123-12128. M. V. Rockman, L. Kruglyak. Genetics of global gene expression. Nature reviews. Genetics, 7 (11), 2006, p. 862-72. X. Zhu, M. Gerstein, M. Snyder. Getting connected: analysis and principles of biological networks. Genes & development, 21 (9), 2007, p. 1010-24. T. M. Przytycka, M. Singh, D. K. Slonim. Toward the dynamic interactome: it's about time. Briefings in bioinformatics, 11 (1), 2010, p. 15-29. S. Suthram, A. Beyer, R. M. Karp, Y. Eldar, T. Ideker. eQED: an efficient method for interpreting eQTL associations using protein networks. Molecular systems biology, 4 (162), 2008, p. 162. J. Zhu, B. Zhang, E. N. Smith, B. Drees, R. B. Brem, L. Kruglyak, R. E. Bumgarner, E. E. Schadt. Integrating large-scale functional genomic data to dissect the complexity of yeast regulatory networks. Nature genetics, 40 (7), 2008, p. 854-61. Y. Huang, S. Wuchty, M. T. Ferdig, T. M. Przytycka. Graph theoretical approach to study eQTL: a case study of Plasmodium falciparum. Bioinformatics (Oxford, England), 25 (12), 2009, p. i15-20. S. Lee, A. M. Dudley, D. Drubin, P. A. Silver, N. J. Krogan, D. Pe'er, D. Koller. Learning a prior on regulatory potential from eQTL data. PLoS genetics, 5 (1), 2009, p. e1000358.

1 0

C. Lu general exam
by Melissa M. Lawson 11 Oct '10

11 Oct '10

Cynthia (Jingwan) Lu will present her research seminar/general exam on Thursday October 14 at 1PM in Room 402. The members of her committee are: Adam Finkelstein, advisor, Szymon Rusinkiewicz, and Bernard Chazelle. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. --------------------------- Abstract : Interactive Stylization of Moving Imagery with temporal coherence Manually creating artwork is a creative but painstaking process. For applications like advertisement, games and video animation, there is an opportunity to use non-photorealistic rendering (NPR) techniques to alleviate the labor of creating stylized imagery. In such applications, however, both interactivity and flexibility are crucial for supporting creative control. Moreover, for stylization of moving imagery an additional challenge lies in maintaining temporal coherence. Resulting animation and video sequences should be support continuity when applying stylization to avoid annoying artifacts such as flickering. In this talk, I present two stylization systems that interact with the artists to generate imagery for different artistic styles. By providing input (still images, video or 3D models), painting sample textures and experimenting with system parameters, the artists can produce stylized and coherent rendering results immediately. The first project focuses on painting surfaces in the scene with visible marks. We apply stroke-based techniques to emulate the layer-by-layer painting process. Temporal coherence is maintained by modeling strokes as independent moving particles guided by optical flow. We describe an algorithm that is executed entirely on GPU to produce high quality results at interactive rates. The second project focuses on the generation of line drawings from 3D models. Important lines of the input are extracted and modeled as snakes - active contours tracking the visible boundaries in the scene. We stylize the active contours by fitting different types of curves, including straight line segments, cubic splines and clothoids. Additional stylization is introduced by adding small-scale synthesized offsets with respect to the brush path, and by varying the width of the brush strokes at different contour samples. Papers: 1. KALNINS , R. D., MARKOSIAN , L., MEIER , B. J., KOWALSKI , M. A., LEE , J. C., DAVIDSON , P. L., WEBB , M., HUGHES , J. F., AND FINKELSTEIN , A. 2002. WYSIWYG NPR: drawing strokes directly on 3D models. In Proceedings of SIGGRAPH 2002, 755–762. 2. KALNINS , R. D., DAVIDSON , P. L., MARKOSIAN , L., AND FINKELSTEIN , A. 2003. Coherent stylized silhouettes. ACM Transactions on Graphics 22, 3 (July), 856–861. 3. HAYS , J., AND ESSA , I. 2004. Image and video based painterly animation. In Proceedings of NPAR 2004, 113–120. 4. VANDERHAEGHE , D., BARLA , P., THOLLOT, J., AND SILLION , F. 2007. Dynamic point distribution for stroke-based rendering. In Rendering Techniques 2007 (Proceedings of the Eurographics Symposium on Rendering), 139–146. 5. B OUSSEAU , A., NEYRET, F., THOLLOT, J., AND SALESIN , D. 2007. Video watercolorization using bidirectional texture advection. In Proceedings of SIGGRAPH 2007, 104. 6. Aseem Agarwala, Aaron Hertzmann, David H. Salesin, and Steven M. Seitz. Keyframe- based tracking for rotoscoping and animation. In SIGGRAPH '04: ACM SIGGRAPH 2004 Papers, pages 584-591, New York, NY, USA, 2004. ACM 7. Aaron Hertzmann, "A Survey of Stroke-Based Rendering," IEEE Computer Graphics and Applications, vol. 23, no. 4, pp. 70-81, July/Aug. 2003 8. Bénard, P., Bousseau, A., and Thollot, J. 2009. Dynamic solid textures for real-time coherent stylization. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ACM, 121--127. 9. Aaron Hertzmann. Paint by relaxation. In Computer Graphics International 2001, pages 47 54, July 2001. 10. L Lin, K Zeng, H Lv, Y Wang, Y Xu, SC Zhu. Painterly animation using video semantics and feature correspondence. In Proceedings of NPAR 2010, 73-80. Book: Non-Photorealistic Rendering Bruce Gooch, Amy Ashurst Gooch Publisher: AK Peters, Ltd. (July 2001) ISBN-10: 1568811330 ISBN-13: 978-1568811338

1 0

Tea starts at 4:00PM
by Michele J. Brown 06 Oct '10

06 Oct '10

in the Tea Room Followed by: "Probabilistic Models for Holistic Scene Understanding" Daphne Koller, Stanford University Wednesday, October 6, 2010, 4:30pm Small Auditorium CS 105

1 0

C Barnes preFPO
by Melissa Lawson 06 Oct '10

06 Oct '10

Connelly Barnes will present his preFPO on Wednesday October 13 at 3PM in Room 302 (note room!). The members of his committee are: Adam Finkelstein, advisor; Szymon Rusinkiewicz and Dan Goldman (Adobe), readers; Tom Funkhouser and Bob Sedgewick, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------------- PatchMatch: A Fast Randomized Matching Algorithm with Applications to Images, Videos, and 3D Volumes Abstract: This thesis presents a novel fast randomized matching algorithm for finding correspondences between small local regions of signals. We also explore a wide variety of applications of this new fast randomized matching technique. The core matching algorithm, which we call PatchMatch, can find similar regions or "patches" of an image one to two orders of magnitude faster than previous techniques. The algorithm requires only very loose assumptions that neighboring correspondences tend to be similar or "coherent" in order to quickly converge to an approximate solution. Our subsequent research has shown that the matching algorithm is quite generic, and can be extended to work on video summarization, computer vision problems, collections of images (ongoing work), and 3D volumes (ongoing work). Our fully generalized algorithm works on a variety of 2D and 3D signals in quite disparate application domains, gaining speed-ups over alternative techniques in a number of areas. We have explored many applications of this matching algorithm. In computer graphics, we have explored removing unwanted objects from images, seamlessly moving objects in images, changing image aspect ratios, and video summarization. In computer vision we have explored denoising images, object detection, detecting image forgeries, and detecting symmetries. In our ongoing work we plan to also apply our algorithm to collections of images, and producing hybrids from a set of input exemplar meshes. We finally will discuss how the statistics of the inputs relate to convergence of our algorithm, the limitations of our algorithm, and areas for future research.

1 0

M Hoffman FPO
by Melissa Lawson 06 Oct '10

06 Oct '10

Matt Hoffman will present his FPO on Tuesday October 12 at 4PM in Room 302 (note room!). The members of his committee are: Perry Cook, advisor; David Blei and Ken Steiglitz, readers; Rob Schapire and Adam Finkelstein, nonreaders. A copy of his thesis, "Probabilistic Graphical Models for the Analysis and Synthesis of Musical Audio" is on display in Room 310. Everyone is invited to attend his talk.

1 0

Distinguished Colloquium Speaker, Oct 6- Daphne Koller
by Nicole E. Wagenblast 06 Oct '10

06 Oct '10

Probabilistic Models for Holistic Scene Understanding Daphne Koller, Stanford University Wednesday, October 6, 2010, 4:30pm Small Auditorium CS 105 Over recent years, computer vision has made great strides towards annotating parts of an image with symbolic labels, such as object categories or segment types. However, we are still far from the ultimate goal of providing a semantic description of an image, such as "a man, walking a dog on a sidewalk, carrying a backpack". In this talk, I will describe our work in this direction, which uses machine learning to construct richly structured, probabilistic models of multiple scene components. We demonstrate the value of such modeling for improvements in basic tasks such as image segmentation and object detection, as well as for making more semantic distinctions regarding shape and activity. The learning of such expressive models poses new challenges, especially when available training data is limited or only weakly labeled. I will describe novel machine learning methods that can train models using distantly or weakly labeled data, thereby making use of much larger amounts of available data. Daphne Koller received her BSc and MSc degrees from the Hebrew University of Jerusalem, Israel, and her PhD from Stanford University in 1993. After a two-year postdoc at Berkeley, she returned to Stanford, where she is now a Professor in the Computer Science Department. Her main research interest is in developing and using machine learning and probabilistic methods to model and analyze complex domains. Her current research projects include models in computational biology and in extracting semantic meaning from sensor data of the physical world. Daphne Koller is the author of over 150 refereed publications, which have appeared in venues spanning Science, Nature Genetics, the Journal of Games and Economic Behavior, and a variety of conferences and journals in AI and Computer Science. She has received 9 best paper or best student paper awards, in conferences whose areas span computer vision (ECCV), artificial intelligence (IJCAI), natural language (EMNLP), machine learning (NIPS and UAI), and computational biology (ISMB). She has given keynote talks at over 10 different major conferences, also spanning a variety of areas. She was the program co-chair of the NIPS 2007 and UAI 2001 conferences, and has served on numerous program committees and as associate editor of the Journal of Artificial Intelligence Research and of the Machine Learning Journal. She was awarded the Arthur Samuel Thesis Award in 1994, the Sloan Foundation Faculty Fellowship in 1996, the ONR Young Investigator Award in 1998, the Presidential Early Career Award for Scientists and Engineers (PECASE) in 1999, the IJCAI Computers and Thought Award in 2001, the Cox Medal for excellence in fostering undergraduate research at Stanford in 2003, the MacArthur Foundation Fellowship in 2004, the ACM/Infosys award in 2008, and the Rajeev Motwani Endowed Chair in 2010.

1 1

2pm Fri Oct 1 talk on predicting faults in federated distributed systems
by Jennifer Rexford 01 Oct '10

01 Oct '10

peaker: Professor Dejan Kostic, EPFL Title: Predicting Faults in Heterogeneous, Federated Distributed Systems Date/time: 2:00-3:00pm on Friday October 1 Location: CS 302 Abstract: It is notoriously difficult to make distributed systems reliable. This becomes even harder in the case of the widely-deployed systems that become heterogeneous and federated. The set of routers in charge of the inter-domain routing in the Internet is a prime example of such a system. The unanticipated interaction of nodes under seemingly valid configuration changes and local fault-handling can have a profound effect. For example, the Internet has suffered from multiple IP prefix hijackings, as well as performance and reliability problems due to emergent behavior resulting from a local session reset. We argue that the key step in making these systems reliable is the need to automatically predict faults. In this talk, I will describe the design and implementation of DiCE, a system that uses temporal and spatial awareness to predict faults in heterogeneous, federated systems. Our live evaluation in the testbed shows that DiCE quickly and successfully predicts two important classes of faults, operator mistakes and programming errors, that have plagued BGP routing in the Internet. Joint work with Marco Canini, Vojin Jovanovic, and Gautam Kumar Bio: Dejan Kostić obtained his Ph.D. in Computer Science at the Duke University, under Amin Vahdat. He spent the last two years of his studies and a brief stay as a postdoctoral scholar at the University of California, San Diego. He received his Master of Science degree in Computer Science from the University of Texas at Dallas, and his Bachelor of Science degree in Computer Engineering and Information Technology from the University of Belgrade (ETF), Serbia. In January 2006, he started as a tenure-track assistant professor at the School of Computer and Communications Sciences at EPFL (Ecole Polytechnique Fédérale de Lausanne), Switzerland. In 2010, he received a European Research Council (ERC) Starting Investigator Award.

1 0

4:30pm Wed Sep 29 colloquium by Michael Mitzenmacher
by Jennifer Rexford 28 Sep '10

28 Sep '10

Some Open Questions Related to Cuckoo Hashing Michael Mitzenmacher, Harvard Wednesday, September 29 4:30pm in CS 105 (with tea at 4pm in the 2nd floor tea room) In this talk, we will describe cuckoo hashing, a recently developed hashing scheme that offers the benefits of very high memory utilization and worst-case constant lookup times. We then discuss recent work in the area, including theoretical bounds on performance, practical methods for improving performance, and implementations on a GPU. Along the way, we will suggest several remaining open questions. The talk will require no prior background on cuckoo hashing, and is aimed for a wide audience, including both theory and systems. Michael Mitzenmacher is a Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University. Michael has authored or co-authored over 150 conference and journal publications on a variety of topics, including Internet algorithms, hashing, load-balancing, erasure codes, error-correcting codes, compression, bin-packing, and power laws. His work on low-density parity-check codes received the 2002 IEEE Information Theory Society Best Paper Award and the 2009 SIGCOMM Test of Time Award. His textbook on probabilistic techniques in computer science, co-written with Eli Upfal, was published in 2005 by Cambridge University Press.

2 1

2pm Fri Oct 1 talk on "predicting faults in heterogenous federated distributed systems"
by Jennifer Rexford 24 Sep '10

24 Sep '10

Speaker: Professor Dejan Kostic, EPFL Title: Predicting Faults in Heterogeneous, Federated Distributed Systems Date/time: 2:00-3:00pm on Friday October 1 Location: CS 302 Abstract: It is notoriously difficult to make distributed systems reliable. This becomes even harder in the case of the widely-deployed systems that become heterogeneous and federated. The set of routers in charge of the inter-domain routing in the Internet is a prime example of such a system. The unanticipated interaction of nodes under seemingly valid configuration changes and local fault-handling can have a profound effect. For example, the Internet has suffered from multiple IP prefix hijackings, as well as performance and reliability problems due to emergent behavior resulting from a local session reset. We argue that the key step in making these systems reliable is the need to automatically predict faults. In this talk, I will describe the design and implementation of DiCE, a system that uses temporal and spatial awareness to predict faults in heterogeneous, federated systems. Our live evaluation in the testbed shows that DiCE quickly and successfully predicts two important classes of faults, operator mistakes and programming errors, that have plagued BGP routing in the Internet. Joint work with Marco Canini, Vojin Jovanovic, and Gautam Kumar Bio: Dejan Kostić obtained his Ph.D. in Computer Science at the Duke University, under Amin Vahdat. He spent the last two years of his studies and a brief stay as a postdoctoral scholar at the University of California, San Diego. He received his Master of Science degree in Computer Science from the University of Texas at Dallas, and his Bachelor of Science degree in Computer Engineering and Information Technology from the University of Belgrade (ETF), Serbia. In January 2006, he started as a tenure-track assistant professor at the School of Computer and Communications Sciences at EPFL (Ecole Polytechnique Fédérale de Lausanne), Switzerland. In 2010, he received a European Research Council (ERC) Starting Investigator Award. His interests include Distributed Systems, Computer Networks, Operating Systems, and Mobile Computing.

1 0

Colloquium Speaker, Sept. 22- Dick Sites
by Nicole E. Wagenblast 21 Sep '10

21 Sep '10

Identifying Dark Latency Richard L. Sites, Google, Inc. Wednesday, September 22, 2010, 4:30 PM Small Small Auditorium CS105 In astronomy and cosmology, dark matter is hypothetical matter that is undetectable by its emitted radiation, but whose presence can be inferred from gravitational effects on visible matter. [Wikipedia] By analogy, dark latency in software is latency that is undetectable directly, but whose presence can be inferred from overall application delays. We bring four tools to bear to observe dark latency in some Google web services, then identify and fix several root causes, in low-level Google libraries and in the TCP stack. The talk makes a case for building and using very low-overhead tools to do bursty tracing of hundreds of thousands of timestamped events per second. A methodology of time-aligning multiple traces (remote procedure call, network, CPU, and lock-contention) across scores of interacting machines is the minimum needed to understand some sources of latency in real web services. Dick Sites is a Senior Staff Engineer at Google, where he has worked for 6 years. He previously worked at Adobe Systems, Digital Equipment Corporation, Hewlett-Packard, Burroughs, and IBM. His accomplishments include co-architecting the DEC Alpha computers, advancing the art of binary translation for computer executables, adding electronic book encryption to Adobe Acrobat, decoding image metadata for Photoshop, and building various computer performance monitoring and tracing tools at the above companies. He also taught Computer Science for four years at UC/San Diego. Most recently he has been working on Unicode text processing and on CPU and network performance analysis at Google. Dr. Sites holds a PhD degree in Computer Science from Stanford and a BS degree in Mathematics from MIT. He also attended the Master's program in Computer Science at University of North Carolina 1969-70. He holds 34 patents and was recently elected to the U.S. National Academy of Engineering.

1 0