- talks - lists.cs.princeton.edu

A Wong general exam
by Melissa Lawson 05 May '10

05 May '10

Aaron Wong will present his research seminar/general exam on Tuesday May 11 at 2PM in Room 402. The members of his committee are: Olga Troyanskaya (advisor), Mona Singh, and Andrea LaPaugh. 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 ----------------------------- A comparative analysis of heterogenous biological networks across diverse organisms With the advent of modern sequencing technologies, high-throughput genomics data are being generated in diverse organisms. Historically, we leveraged these data to construct a single biological network for each organism by integrating heterogeneous datasets spanning thousands of experiments. These integrated functional networks are fully-connected, where each node represents a gene and edge weights describe the probability that a pair of genes participate in a similar biological process. Thus, each network attempts to capture the available experimental data in a particular organism and predict gene-function relationships. As barriers to entry lower, we will have increasingly more genomics data for more diverse organisms. There is great interest in comparing the genomes of different organisms, illuminating the evolutionary processes that have shaped their genomes. In this study, we use a previously described method that extends networks of gene relationships to maps of gene function and construct functional maps in two organisms. We use Gene Ontology to classify genes into functional groups and compare the network properties of these gene groups across functional networks. We attempt to characterize patterns of functional evolution by comparing network cohesiveness of functional groups, identifying both conserved and divergent biological processes. Further, we describe inter-process relationships, conserved among functional maps, to identify patterns of co-regulation between processes. ----------------------------- Book: [1] Artificial Intelligence: A Modern Approach (Second Edition) by Stuart Russell and Peter Norvig - section V (Uncertain knowledge and reasoning), section VI (Learning) Papers: [1] Alter, O., P. O. Brown, and D. Botstein, 2003 Generalized singular value decomposition for comparative analysis of genome-scale expression data sets of two different organisms. Proc Natl Acad Sci U S A 100: 3351-3356. [2] Kriston L. McGary, Tae Joo Park, John O. Woods, Hye Ji Cha, John B. Wallingford, and Edward M. Marcotte, Proc Natl Acad Sci USA Systematic discovery of non-obvious human disease models through orthologous phenotypes [3] Gandhi, T. K., J. Zhong, S. Mathivanan, L. Karthick, et al., 2006 Analysis of the human protein interactome and comparison with yeast, worm and fly interaction datasets. Nat Genet 38: 285-293. [4] Goh, K. I., M. E. Cusick, D. Valle, B. Childs, et al., 2007 The human disease network. Proc Natl Acad Sci U S A 104: 8685-8690. [5] Huttenhower, C., and O. G. Troyanskaya, 2006 Bayesian data integration: a functional perspective. Comput Syst Bioinformatics Conf 341-351. [6] Huttenhower, C., E. M. Haley, M. A. Hibbs, V. Dumeaux, et al., 2009 Exploring the human genome with functional maps. Genome Res 19: 1093-1106. [7] Myers, C. L., D. R. Barrett, M. A. Hibbs, C. Huttenhower, and O. G. Troyanskaya, 2006 Finding function: evaluation methods for functional genomic data. BMC Genomics 7: 187. [8] Sharan, R., S. Suthram, R. M. Kelley, T. Kuhn, et al., 2005 Conserved patterns of protein interaction in multiple species. Proc Natl Acad Sci U S A 102: 1974-1979. [9] Storey, J. D., and R. Tibshirani, 2003 Statistical significance for genomewide studies. Proc Natl Acad Sci U S A 100: 9440-9445. [10] Watts, D. J., and S. H. Strogatz, 1998 Collective dynamics of 'small-world' networks. Nature 393: 440-442.

1 0

T Lee general exam
by Melissa Lawson 04 May '10

04 May '10

Tim Lee will present his research seminar/general exam on Monday May 10 at 2PM in Room 402. The members of his committee are: Ed Felten (advisor), David Blei, and Mike Freedman. 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: Recent years have seen increasing interest in the problem of web- enabled government transparency. Last year, I helped create RECAP, a FireFox plugin that helps users to build a free, open repository of federal court records. One of the key challenges in building the RECAP archive is privacy. Parties to court cases are supposed to redact sensitive information such as Social Security numbers and bank account numbers, but they often fail to do so, creating a potential privacy problem if these documents are made available for free on the web. With more than 2 million documents in our repository, there are too many documents for manual human inspection. And releasing the documents without filtering them first could compromise the privacy of Americans who are the subjects of those records. In my talk I will describe my use of machine learning techniques to identify documents requiring redaction. Starting with 5,926 documents in the RECAP archive that had already been redacted by human beings and 17,021 randomly-selected non-redacted documents, I built several classifiers: one using a logistic regression, and several others using combinations of boosting and topic models. The latter classifiers proved highly accurate, with the best having an area under the ROC curve of 0.9735. This technique has immediate application to the judicial redaction problem. Because redacted documents are highly similar to documents that should have been redacted, a classifier trained on the former will also be good at finding the latter. These classifiers dramatically reduce the amount of human labor required to find documents with sensitive information in our RECAP archive, as well as in the much larger PACER archive. Variants of this technique could have wide-ranging applications, including protecting attorney-client privilege during the discovery process and protecting national security when releasing some kinds of executive branch documents. -- Reading List: Textbooks [1] Stuart Russell and Peter Norvig, "Artificial Intelligence: A Modern Approach." Chapters 3-6, 13-15, 18-21 [2] Christopher M. Bishop, "Pattern Recognition and Machine Learning", Chapters 3, 4 Papers [3] Mark Steyvers and Tom Griffiths, "Probabilistic Topic Models." http://psiexp.ss.uci.edu/research/papers/SteyversGriffithsLSABookFormatted.… [4] David M. Blei and John D. Lafferty, "Topic Models." http://www.cs.princeton.edu/~blei/papers/BleiLafferty2009.pdf [5] Robert E. Schapire and Yoram Singer. "BoosTexter: A Boosting-based System for Text Categorization." Machine Learning, 2000. http://www.cis.upenn.edu/~mkearns/finread/boostexter.pdf [6] David Robinson, Harlan Yu, William Zeller and Edward W. Felten, "Government Data and the Invisible Hand." Yale Journal of Law and Technology, Fall 2008. http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1138083 [7] Peter A. Winn, "Judicial Information Management in an Electronic Age: Old Standards, New Challenges." Federal Courts Law Review. http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1438674 [8] Peter W. Martin, "Online Access to Court Records - from Documents to Data, Particulars to Patterns." Villanova Law Review, vol. 53, no. 5 (2008) http://scholarship.law.cornell.edu/cgi/viewcontent.cgi?article=1092&context…

1 0

N Johnson general exam
by Melissa Lawson 04 May '10

04 May '10

Nick Johnson will present his research seminar/general exam on Monday May 10 at 10AM in Room 402. The members of his committee are: David August (advisor), Andrew Appel, and Brian Kernighan. 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. -------------------------------------------- Effective Composition of Optimizing Transformations via Obstacle Identification Abstract Optimizing transformations interact in complicated, non-linear and often unknown ways. This prevents most compilers from applying transformations in an optimal manner. Multicore exacerbates this problem; the performance difference between the best and average transform sequences is orders of magnitude. Common practice uses applicability and profitability guards to decide whether each transformation should be applied greedily or not at all, but may miss intermediate strategies with better performance. I present the obstacle identification technique, which uses the dual of those guards to identify limiting qualities of the program structures. By repeatedly relaxing program structure and retesting the guards, we enumerate those relaxations which improve applicability or profitability (obstacles). We demonstrate the promise of the obstacle identification technique by applying it to the problem of interacting transformations. This technique offers a competitive solution. References [1] F. Agakov, E. Bonilla, J. Cavazos, B. Franke, G. Fursin, M. F. P. O'Boyle, J. Thomson, M. Toussaint, and C. K. I. Williams. Using machine learning to focus iterative optimization. In CGO '06: Proceedings of the International Symposium on Code Generation and Optimization, pages 295-305, Washington, DC, USA, 2006. IEEE Computer Society. [2] L. Almagor, Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steven W. Reeves, Devika Subramanian, Linda Torczon, and Todd Waterman. Finding effective compilation sequences. In LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, pages 231-239, New York, NY, USA, 2004. ACM Press. [3] Andrew W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998. [4] Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steven Reeves, Devika Subramanian, Linda Torczon, and Todd Waterman. ACME: Adaptive compilation made efficient. In LCTES '05: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, pages 69{77, New York, NY, USA, 2005. ACM. [5] J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9:319-349, July 1987. [6] Jialu Huang, Arun Raman, Yun Zhang, Thomas B. Jablin, Tzu-Han Hung, and David I. August. Decoupled Software Pipelining Creates Parallelization Opportunities. In Proceedings of the 2010 International Symposium on Code Generation and Optimization, April 2010. [7] S. Muchnick. Advanced Compiler Design and Implementation. Morgan- Kaufmann Publishers, San Francisco, CA, 1997. [8] Easwaran Raman, Guilherme Ottoni, Arun Raman, Matthew J. Bridges, and David I. August. Parallel-stage decoupled software pipelining. In CGO '08: Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, pages 114-123, New York, NY, USA, 2008. ACM. [9] Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. Equality saturation: A new approach to optimization. In POPL '10: Proceedings of the 37th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 2010. [10] Spyridon Triantafyllis, Manish Vachharajani, and David I. August. Compiler optimization-space exploration. Journal of Instruction-Level Parallelism, 7, 2005. [11] M. Wolf, D. Maydan, and D. Chen. Combining loop transformations considering caches and scheduling. In Proceedings of the 29th Annual International Symposium on Microarchitecture, pages 274-286, December 1996.

1 0

3pm Tue May 4 talk on algebraic modeling of policy-based routing
by Jennifer Rexford 03 May '10

03 May '10

Speaker: Tim Griffin, University of Cambridge Title: Exploring the Stratified Shortest Paths Problem Date/time: 3pm Tuesday May 4 Location: room 302 in the Computer Science building Abstract: The Border Gateway Protocol (BGP) is the keystone among Internet routing protocols as it maintains connectivity in the entire global Internet. BGP has evolved into a rather mysterious beast. Theoretical work over the last ten years has made it clear that BGP represents something novel in the context of routing protocols: BGP does not compute globally optimal paths, but only locally optimal paths. The talk will explain how this exotic type of routing can be understood in an algebraic setting. The Stratified Shortest-Paths Problem (SSPP) is presented as a very simple example of this type of algebra. The SSPP is meant to capture the essence of a BGP-like path problem without BGP's many operational complexities. Bio: Tim Griffin is a Senior Lecturer and Fellow at King's College, University of Cambridge. His research interests include network protocol design and analysis, with a focus on Internet routing protocols.

1 0

Vladimir Kim general exam
by Melissa Lawson 03 May '10

03 May '10

Vladimir Kim will present his research seminar/general exam on Friday May 7 at 10AM in Room 302 (note room!). The members of his committee are: Tom Funkhouser (advisor), Adam Finkelstein, and Bernard Chazelle. His abstract and reading list follow below. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. ----------------------------------------- Abstract: I present a framework for symmetry-guided texture synthesis and processing. It is motivated by the long-standing problem of how to optimize, transfer, and control the spatial patterns in textures. The key idea is that symmetry representations that measure autocorrelations with respect to all transformations of a group are a natural way to describe spatial patterns in many real-world textures. To leverage this idea, we provide methods to transfer symmetry representations from one texture to another, process the symmetries of a texture, and optimize textures with respect to properties of their symmetry representations. These methods are automatic and robust, as they don't require explicit detection of discrete symmetries. Applications are investigated for optimizing, processing and transferring symmetries and textures. Reading List: A planar-reflective symmetry transform for 3D shapes Author Podolak, Joshua and Shilane, Philip and Golovinskiy, Aleksey and Rusinkiewicz, Szymon and Funkhouser, Thomas Booktitle ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2006 Discovering Structural Regularity in 3D Geometry Author M. Pauly and N. J. Mitra and J. Wallner and H. Pottmann and L. Guibas Journal ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2008 Volume 27 Symmetrization (inproceedings) Author N. J. Mitra and L. Guibas and M. Pauly Booktitle ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2007 Partial and Approximate Symmetry Detection for 3D Geometry Author N. J. Mitra and L. Guibas and M. Pauly Booktitle ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2006 Volume 25 Number 3 Image De-fencing (article) Author Yanxi Liu and Tamara Belkina and James H. Hays and Roberto Lublinerman Journal International Conference on Computer Vision Year 2008 Month June Near Regular Texture Analysis and Manipulation Author Yanxi Liu and Wen-Chieh Lin and James H. Hays Journal ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2004 Volume 23 Number 1 Quantitative Evaluation of Near Regular Texture Synthesis Algorithms Author Lin, Wen-Chieh and Hays, James and Wu, Chenyu and Liu, Yanxi and Kwatra, Vivek Booktitle Computer Vision and Pattern Recognition Year 2006 Pages 427--434 A Reflective Symmetry Descriptor for 3D Models Author M. Kazhdan and B. Chazelle and D. Dobkin and T. Funkhouser and S. Rusinkiewicz Journal Algorithmica Year 2003 Pyramid-based texture analysis/synthesis Author Heeger, David J. and Bergen, James R. Booktitle ACM Transactions on Graphics (Proc. SIGGRAPH) Year 1995 Address New York, NY, USA Texture Synthesis by Non-parametric Sampling Author Alexei A. Efros and Thomas K. Leung Booktitle IEEE ICCV Year 1999 Month September Image Quilting for Texture Synthesis and Transfer Author Alexei A. Efros and William T. Freeman Journal ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2001 As-Rigid-As-Possible Shape Manipulation Author Takeo Igarashi and Tomer Moscovich and John F. Hughes Journal ACM Transactions on Graphics (Proc. SIGGRAPH) Year 2005 Volume 24 Number 3

1 0

W Mulzer FPO
by Melissa Lawson 29 Apr '10

29 Apr '10

Wolfgang Mulzer will present his FPO on Wednesday May 5 at 3PM in Room 402. The members of his committee are: Bernard Chazelle, advisor; David Dobkin and Bob Tarjan, readers; Sanjeev Arora and Moses Charikar, nonreaders. A copy of his thesis, "Low-Entropy Computational Geometry", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Colloquium Speaker, Tues April 27- Youngmoo Kim
by Nicole E. Wagenblast 26 Apr '10

26 Apr '10

Exploring Emotion and Expression through Music Technology Youngmoo Kim, Drexel Tuesday, April 27, 2010 -4:30pm Small Auditorium CS105 Over the past few decades, advances in computing and signal processing have had a profound impact on music performance, recording, and reproduction. The universal appeal of music, however, lies in its ability to provide expression to our feelings, and the recognition or utilization of these concepts computationally remains beyond the capability of current systems. Expression and emotion are, of course, highly subjective terms, ill-suited to quantitative definition and exploration. There may be considerable disagreement among listeners regarding the emotional content of a particular piece, and the expressive intentions of a highly skilled performer can be equally difficult to quantify. But innovations in sensing, human-computer interaction, and machine learning have the potential to reveal insights into these opaque domains. This presentation will highlight research by the Music & Entertainment Technology Laboratory (MET-lab) at Drexel University exploring music, emotion, and creative expression under the common vision of making music more interactive and accessible for both musicians and non-musicians. These projects encompass the recognition of emotion, such as a system for dynamic musical mood prediction and a collaborative web game for the collection of emotional annotations, as well as interfaces for expressive performance, including a novel electromagnetic approach to shaping the sound of the acoustic piano and a user-friendly controller for remixing music in terms of emotion. These and other MET-lab efforts are closely coupled with educational initiatives, many of which have been deployed in K-12 outreach programs in the Philadelphia region, to promote learning in Science, Technology, Engineering, and Mathematics (STEM). Youngmoo Kim is an Assistant Professor of Electrical and Computer Engineering at Drexel University. His research group, the Music & Entertainment Technology Laboratory (MET-lab) focuses on the machine understanding of audio, particularly for music information retrieval. Other areas of active research at MET-lab include analysis-synthesis of sound, human-machine interfaces and robotics for expressive interaction, and K-12 outreach for engineering, science, and mathematics education. Youngmoo received his Ph.D. from the MIT Media Lab in 2003 and also holds Masters degrees in Electrical Engineering and Music (Vocal Performance Practice) from Stanford University. He served as a member of the MPEG standards committee, contributing to the MPEG-4 and MPEG-7 audio standards, and he co-chaired the 2008 International Conference on Music Information Retrieval (hosted at Drexel). His research is supported by the National Science Foundation and the NAMM Foundation, including an NSF CAREER award in 2007.

1 0

11am Wed May 5 talk on data center networks by in room CS 402
by Jennifer Rexford 19 Apr '10

19 Apr '10

SPAIN: COTS Data-Center Ethernet for Multipathing over Arbitrary Topologies Jeff Mogul, HP Labs Operators of data centers want a scalable network fabric that supports high bisection bandwidth and host mobility, but which costs very little to purchase and administer. Ethernet almost solves the problem -- it is cheap and supports high link bandwidths -- but traditional Ethernet does not scale, because its spanning-tree topology forces traffic onto a single tree. Many researchers have described "scalable Ethernet" designs to solve the scaling problem, by enabling the use of multiple paths through the network. However, most such designs require specific wiring topologies, which can create deployment problems, or changes to the network switches, which could obviate the commodity pricing of these parts. In this talk, I will describe SPAIN ("Smart Path Assignment In Networks"). SPAIN provides multipath forwarding using inexpensive, commodity off-the-shelf COTS) Ethernet switches, over arbitrary topologies. SPAIN pre-computes a set of paths that exploit the redundancy in a given network topology, then merges these paths into a set of trees; each tree is mapped as a separate VLAN onto the physical Ethernet. SPAIN requires only minor end-host software modifications, including a simple algorithm that chooses between pre-installed paths to efficiently spread load over the network. We demonstrate SPAIN's ability to improve bisection bandwidth over both simulated and experimental data-center networks. Joint work with Jayaram Mudigonda and Praveen Yalagandula, and with Mohammad Al-Fares (UCSD)

1 0

Colloquium Speaker, Tues, April 20- Avinatan Hassidim
by Nicole E. Wagenblast 19 Apr '10

19 Apr '10

Matching Markets Avinatan Hassidim, MIT Tuesday, April 20, 2010, 4:30 PM Small Auditorium CS105 Matching markets appear in many different scenarios, from college admissions to job search. In the simplest, the deferred acceptance of Gale and Shapley provides a stable solution (also known as a stable marriage) to these problems. It also has the desirable property that for the ``proposing side" it is a dominant strategy to behave truthfully. In this talk, I will focus on a couple of more involved matching markets. The first will be assigning doctors to residencies when there are two body problems. We will discuss the Match, show impossibility results, and present new matching algorithms that satisfy the above properties in a large market . The second will be Internet ad auctions with budgets, where we match between advertisers and slots on the web-page. Based on Joint works with Itai Ashlagi, Mark Braverman, Ron Lavi and Moshe Tennenholtz

1 1

Colloquium Speaker, Mon April 19th- David Sontag
by Nicole E. Wagenblast 15 Apr '10

15 Apr '10

Approximate Inference in Graphical Models using LP Relaxations David Sontag, MIT Monday, April 19th, 2010- 4:30pm Computer Science, Small Auditorium CS105 Graphical models such as Markov random fields have been successfully applied to a wide variety of fields, from computer vision and natural language processing, to computational biology. Exact probabilistic inference is generally intractable in complex models having many dependencies between the variables. In this talk, I will discuss recent work on using linear programming relaxations to perform approximate inference. By solving the LP relaxations in the dual, we obtain efficient message-passing algorithms that, when the relaxations are tight, can provably find the most likely (MAP) configuration. Our algorithms succeed at finding the MAP configuration in protein side-chain placement, protein design, and stereo vision problems. More broadly, this talk will highlight emerging connections between machine learning, polyhedral combinatorics, and combinatorial optimization.

1 0