- talks - lists.cs.princeton.edu

A Boyko general exam
by Melissa Lawson 12 May '10

12 May '10

Aleksey Boyko will present his research seminar/general exam on Tuesday May 18 at 10 AM in Room 402. The members of his committee are: Tom Funkhouser (advisor), Szymon Rusinkiewicz, and Adam Finkelstein. 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: Range scan data provides high resolution 3D information about the real life environment. Urban scans in the form of point clouds are becoming more available. However, point clouds are both noisy, very large, and they do not have semantic labels that associate each point of the scanned surfaces to a specific object. Our goal is to provide means for a meaningful classification of large scale point clouds derived from urban environment range scans. In my talk I will focus on two classes of objects. An important category of objects in an urban landscape consists of roads, streets and driveways. This category represents potentially the largest in size class of objects in a city - the road network. At the same time this class provides a context for other objects, both of a large and small scale - it separates the city into blocks and defines the position of large variety of small scale objects. In order to provide such context it is desirable to have a precise separation of the road surface from the sidewalks, which delimit the road surface. We present an algorithm that takes advantage of available online map information and uses dynamic contours (snakes) to provide an accurate extraction of points belonging to the road surface from the rest of the points. Addressing the rest of the objects we can separate them into large scale objects, such as buildings, and small-scale objects. Due to noisiness of the point cloud data it is harder to address the question of recognition of small-scale objects. [Golovinskiy, et al. 2009] offer numeric evaluation of how well supervised machine learning algorithms are at automatic classification of small objects in a point cloud of an urban environment. We research how making the classification user-guided can improve the rates and accuracy of the classification. We employ online learning (user-guided) and active learning (computer-guided) approach and show that giving user real-time control over the process of learning improves both the rate and the correctness of classification over blind selection of the training set. Reading list: [1] R. J. Campbell and P. J. Flynn. A survey of free-form object representationand recognition techniques. Computer Vision and Image Understanding, 81 doi: 10.1006/cviu.2000.0889 URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.1720&rep=rep1&t… [2] M. Carlberg, J. Andrews, P. Gao, and A. Zakhor. Fast surface reconstruction and segmentation with ground-based and airborne lidar range data. 3DPVT, 2008. URL http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-5.pdf [3] A. Frome, D. Huber, R. Kolluri, T. Bulow, and J. Malik. Recognizing objects in range data using regional point descriptors. ECCV doi: 10.1007/b97871 URL http://www.springerlink.com/content/d4ukq18fpbfe9la6/fulltext.pdf [4] A. Golovinskiy, V. G. Kim, and T. Funkhouser. Shape-based recognition of 3d point clouds in urban environments. ICCV, Sept. 2009. URL http://www.cs.princeton.edu/gfx/pubs/Golovinskiy_2009_SRO/paper.pdf [5] D. Hearn and M. Baker. Computer Graphics with OpenGL. Pearson PrenticeHall, 3 edition, 2004. URL http://www.pearsonhighered.com/educator/product/Computer-Graphics-with-Open… 6.page. [6] A. Jaakkola, J. Hyyppa, H. Hyyppa, and A. Kukko. Retrieval algorithms for road surface modelling using laser-based mobile mapping. Sensors, 8, 2008. doi: 10.3390/s8095238 URL http://www.mdpi.org/sensors/papers/s8095238.pdf [7] A. E. Johnson and M. Hebert. Using spin images for effcient object recognition in cluttered 3d scenes. IEEE PAMI, 1999. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8816&rep=rep1&t… [8] B. C. Matei, Y. Tan, H. S. Sawhney, and R. Kumar. Rapid and scalable 3d object recognition using lidar data. SPIE, 6234, 2006. doi: 10.1117/12.666235 URL http://spiedl.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=PSISDG00… 1000001&idtype=cvips&prog=normal. [9] H. Mayer, I. Laptev, and A. Baumgartner. Multi-scale and snakes for automatic road extraction. ECCV, 1998. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.8855&rep=rep1&t… [10] R. Schnabel, R. Wahl, R. Wessel, and R. Klein. Shape recognition in 3d point clouds. The 16-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, 2008. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.2344&rep=rep1&t… [11] B. Settles. Active learning literature survey. 2009. URL http://pages.cs.wisc.edu/~bsettles/active-learning/ [12] S.P.Clode, F.Rottensteiner, P.Kootsookos, and E.Zelniker. Detection and vectorization of roads from lidar data. PhEngRS, May 2007. URL http://www.asprs.org/publications/pers/2007journal/may/2007_may_517-535.pdf [13] G. Vosselman and Z. Liang. Detection of curbstones in airborne laser scanning data. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 38:3/W8, 2009. URL http://www.itc.nl/personal/vosselman/papers/vosselman2009.paris.pdf =========

1 0

1:30 Mon May 17 talk on network virtualization in CS 105
by Jennifer Rexford 11 May '10

11 May '10

Speaker: Dr. Sanjoy Paul, Infosys, Associate Vice President Title: Network Virtualization applied to the Network of a Communication Service Provider for Enabling Novel Services in Vertical Sectors Date/time: 1:30-2:30pm on Monday May 17 Location: CS 105 (small auditorium) Abstract: Communication technology has advanced significantly over the last decade enabling people to communicate anytime from anywhere using a multiplicity of devices. However, the power of this advancement in communication technology has hardly been leveraged in traditional services industry. Specifically, the vertical service providers, such as the Health Care industry, the Banking industry, the Education industry, and others who require network-based services to efficiently conduct their business reducing their operational expenses, and to provide novel value-added services to their customers generating additional revenue, have hardly been able to leverage the power of the network to their advantage. In the talk, I will describe several applications from the services industry that can be built on a platform (referred to as Network as a Service or NaaS platform) based on the concept of network virtualization and shows how various parties involved in providing the services are economically incentivized to make them feasible in real life. The NaaS platform enables Communication Service Providers (CSPs) to work collaboratively with Vertical Service Providers (VSPs) to offer novel services leveraging their existing network infrastructure through the techniques of network virtualization. This solution enables CSPs to generate new revenue without additional capital expenditure, and in addition, also enables VSPs to generate additional revenue via novel value-added service offerings to their customers without incurring any capital expenditure either. Thus, this model of offering services provides a win-win value proposition to both CSPs as well as to VSPs. NaaS Platform is being built at Infosys Technologies Limited. In course of my presentation, I’ll describe a high-level architecture of the platform and discuss how various functional blocks in the architecture are used synergistically to deliver a novel service called On Demand Health Care (ODHC). Bio: Sanjoy Paul (sanjoy_paul(a)infosys.com) is Associate Vice President, General Manager-Research and Head of Convergence Lab at Infosys Technologies Limited where he heads research and innovation in the field of Communications, Media and Entertainment. Prior to that, he was a Research Professor at WINLAB, Rutgers University, and Founder of RelevantAd Technologies Inc. Before that Sanjoy spent five years as the Director of Wireless Networking Research at Bell Labs, Lucent Technologies, and as the CTO of two start-up companies (Edgix and WhenU) based in New York. In a previous tenure at Bell Labs as a Distinguished Member of Technical Staff, Sanjoy was the chief architect of Lucent's IPWorX Caching and Content Distribution product line. Sanjoy has authored a book on Multicasting, published over 100 papers in International Journals and refereed Conference Proceedings, authored over 80 US patents (28 granted, 50+ pending), and is the co-recipient of 1997 William R. Bennett award from IEEE Communications Society for the best original paper in IEEE/ACM Transactions on Networking. He holds a Bachelor of Technology degree from IIT Kharagpur, India, an M.S and a Ph.D. degree from the University of Maryland, College Park, and an MBA from the Wharton Business School, University of Pennsylvania. Sanjoy is a Fellow of IEEE and a Member of the ACM.

1 0

A Soviani preFPO
by Melissa Lawson 11 May '10

11 May '10

Adrian Soviani will present his preFPO on Monday May 17 at 4PM in Room 402. The members of his committee are: J.P. Singh, advisor; Kai Li and David August, readers; Brian Kernighan and Ken Steiglitz, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------------------- Building scalable parallel applications remains a difficult task due to implementation complexity, performance portability, and inability to understand hidden costs and bottlenecks. Specific machine architectures and software layers further influence application efficiency and performance transparency, making optimization a time consuming burden. The parallel programming model has a great impact on addressing these issues and reaching a good tradeoff between implementation effort and application efficiency. This thesis presents a hybrid SPMD - Coarse Grain Dataflow programming model (CGD) that describes data and task parallelism at high level. CGD applications are specified as dependencies between computation modules and data distributions while communication and synchronization are added automatically and optimized for specific architectures. We claim the CGD model can make application development and design space exploration simpler compared to message passing, at the same time providing similar or better performance. Results on the 128 CPU SGI Altix 4700 show our optimized CGD FT is 27% faster than the original NPB 2.3 MPI implementation, the optimized CGD stencil has a 41% advantage over handwritten MPI, while the CGD Barnes-Hut 1M particle benchmark is 15% faster than the pthreads Splash2 implementation. CGD takes advantage of its dataflow semantics and explicit distribution rules to automatically schedule computations and insert, aggregate and overlap communication, simplifying application development and optimization. E.g., the CGD NPB FT implementation requires 85 lines of dataflow and 700 lines of sequential C++ code, while the original MPI implementation has 1260 lines of code and exhibits poorer performance portability.

1 0

S Sachdeva general exam
by Melissa Lawson 11 May '10

11 May '10

Sushant Sachdeva will present his research seminar/general exam on Monday May 17 at 2PM in Room 402. The members of his committee are: Sanjeev Arora (advisor), Moses Charikar, and Bernard Chazelle. 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. ---------------------------------------------------- Title : Parallel Approximation algorithms based on SDPs Abstract: We explore the following question: Can the matrix exponential update method can help us give efficient SDP based parallel approximation algorithms? The matrix multiplicative weights method or the matrix exponential update method, developed by Arora and Kale has proved to be a successful framework to design faster approximation algorithms based on solving semidefinite programs (SDP). Very recently, the method has been used in a work of Jain et al to show that the class of Quantum Interactive Proofs (QIP) is the same as PSPACE. Their work relies on using the matrix exponential update method to solve an exponential sized SDP using a circuit of only polynomial depth. Aside from being a natural question, the aforementioned result strongly hints at the possibility of parallel algorithms based on this method. Luby and Nisan ('93) had shown that (scalar) multiplicative weights method could be used to approximate packing-covering LP's (positive LPs) up to (1+eps) in parallel (EREW PRAM). An eventual goal of the work is to show a matrix analogue of their result. In this work, we give parallel algorithms for solving the MaxCut SDP (up to a multiplicative factor of 1+eps) and finding an O(log n) approximation to balanced separator. Our algorithms require poly(n/eps) processors and time poly(log n/eps). Using the work of Steurer, we can also give an efficient parallel algorithm to solve the 'standard sdp' for any CSP. We will also talk about some results on another problem. In a recent STOC paper, Lee and Moharrami construct a metric (X,d) such that the metric (X,sqrt(d)) can be embedded with constant distortion into L_2 but embedding (X,d) into a negative type metric (L_2-squared) requires distortion at least Omega((log n)^{1/7}). We are able to give a tighter analysis of their construction and improve the bound to Omega((log n)^{1/3}). Joint work with Sanjeev Arora. Reading list ========= A. Books: a. Algorithm Design - Jon Kleinberg, Eva Tardos b. Complexity theory (Chap. 1-8 (basic complexity), 11 and 22 (PCP theorem))- Sanjeev Arora, Boaz Barak B. Papers: � A combinatorial primal-dual approach to semidefinite programs - Sanjeev Arora, Satyen Kale � A parallel approximation algorithm for positive linear programming - Michael Luby, Noam Nisan � Fast SDP algorithms for constraint satisfaction problems- David Steurer � The multiplicative weights update method: A meta-algorithm and applications (Survey) - Sanjeev Arora, Elad Hazan, Satyen Kale � QIP = PSPACE - Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous � Matrix exponentiated gradient updates for on-line learning and bregman projections - Koji Tsuda, Gunner Ratsch and Manfred K. Warmuth � Fast approximation algorithms for fractional packing and covering problems - Serge Plotkin, David Schmoys and Eva Tardos � Online Variance minimization - Manfred K. Warmuth, Dima Kuzmin � Twice Ramanujan Sparsifiers : Joshua Batson, Daniel Spielman, Nikhil Srivastava � An elementary proof of the Restricted Invertibility Theorem : Daniel Spielman, Nikhil Srivastava

1 0

D Shue general exam
by Melissa Lawson 11 May '10

11 May '10

David Shue will present his research seminar/general exam on Monday May 17 at 10AM in Room 402. The members of his committee are: Mike Freedman (advisor), Jennifer Rexford, and Vivek Pai. 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: Routing and Resolution in the SCAFFOLD network architecture With the advent of massively distributed networked services, many of the fundamentally host-centric primitives that lie at the core of the Internet architecture have become misaligned to the needs and challenges of modern online services. Replicated across geographically distributed datacenters, each encompassing myriad instances, these services require more adaptive and flexible mechanisms for dealing with failure, mobility, and load distribution than current approaches allow. Rather than bind these services to rigid host end-points and static locations, the network should enable service-centric communication between equivalent instances across dynamic locales. We present SCAFFOLD, a network architecture that moves from addressable host identifiers to resolvable service identifiers, from individual packets to flows, and from unicast communication to anycast. SCAFFOLD hides network addresses from applications and decouples location from identity to enable dynamic remapping as end-points change, (e.g. due to virtual-machine migration, failover, load shedding, or device mobility), and directs traffic based on successively-refined identifiers to distribute load, scale routing, and limit churn. In this talk we focus on the core anycast-based SCAFFOLD resolution and routing architecture and implementation based on OpenFlow and NOX. We conclude with ongoing work exploring joint service selection and traffic engineering in the datacenter using the SCAFFOLD framework. Reading list: [1] H. Balakrishnan, K. Lakshminarayanan, S. Ratnasamy, S. Shenker, I. Stoica, and M. Walfish. A layered naming architecture for the internet. In SIGCOMM '04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, pages 343-352, New York, NY, USA, 2004. ACM. [2] T. Koponen, M. Chawla, B.-G. Chun, A. Ermolinskiy, K. H. Kim, S. Shenker, and I. Stoica. A data-oriented (and beyond) network architecture. In SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, pages 181-192, New York, NY, USA, 2007. ACM. [3] V. Jacobson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. Briggs, and R. L. Braynard. Networking named content. In CoNEXT '09: Proceedings of the 5th international conference on Emerging networking experiments and technologies, pages 1-12, New York, NY, USA, 2009. ACM. [4] A. Greenberg, G. Hjalmtysson, D. A. Maltz, A. Myers, J. Rexford, G. Xie, H. Yan, J. Zhan, and H. Zhang. A clean slate 4d approach to network control and management. SIGCOMM Comput. Commun. Rev., 35(5):41-54, 2005. [5] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta. Vl2: a scalable and flexible data center network. In SIGCOMM '09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication, pages 51-62, New York, NY, USA, 2009. ACM. [6] R. Niranjan Mysore, A. Pamboris, N. Farrington, N. Huang, P. Miri, S. Radhakrishnan, V. Subramanya, and A. Vahdat. Portland: a scalable fault-tolerant layer 2 data center network fabric. In SIGCOMM '09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication, pages 39-50, New York, NY, USA, 2009. ACM. [7] D. Xu, M. Chiang, and J. Rexford. Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering. In INFOCOM '08, pages 466 -474 [8] W. Jiang, R. Zhang-Shen, J. Rexford, and M. Chiang. Cooperative content distribution and traffic engineering in an ISP network. In SIGMETRICS '09: Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems, pages 239-250, New York, NY, USA, 2009. ACM. [9] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner. Openflow: enabling innovation in campus networks. SIGCOMM Comput. Commun. Rev., 38(2):69-74, 2008. [10] N. Gude, T. Koponen, J. Pettit, B. Pfaff, M. Casado, N. McKeown, and S. Shenker. Nox: towards an operating system for networks. SIGCOMM Comput. Commun. Rev., 38(3):105-110, 2008. Textbook: L. Peterson, B. Davie, Computer Networks: a systems approach, Elsevier, 2007

1 0

L Luo general exam
by Melissa Lawson 07 May '10

07 May '10

Linjie Luo will present his research seminar/general exam on Thursday May 13 at 2PM in room 302 (note room!). The members of his committee are: Szymon Rusinkiewicz (advisor), Tom Funkhouser, and Adam Finkelstein. 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: Texture Reconstruction and Surface Registration in Multi-view Performance Capture Creating high resolution, temporally coherent 3D model sequence in real-time performance capture systems based on multi-view photometric stereo gains increasing interest recently. Accurate correspondences across the captured sequence provide an important basis to improve temporal coherence with useful information from neighboring frames. However correspondence problem is difficult due to the aperture problem, visibility change (occlusion/disocclusion), topology change and inherent ambiguity. In this work, following a previously developed deformation-graph-based coarse matching pass, we use a variant of local ICP algorithm to register adjacent frames in fine scale. To prevent tangential drifting in long sequence, we regularize the correspondences with local isometric constraint. Our result proves effective and robust to local visibility changes. To obtain high resolution and fully texturized models, we resynthesize high resolution detail from normal maps and reconstruct texture by solving Poisson equation on surface. This approach guarantees smooth texture transition between views and optimized coloring in occluded region. READING LIST: [1] Rusinkiewicz, S., and Levoy, M. Efficient Variants of the ICP Algorithm. 3DIM 2001. [2] Chuang, M., Luo, L., Brown, B. J., Rusinkiewicz, S., and Kazhdan, M. Estimating the Laplace-Beltrami Operator by Restricting 3D Functions. SGP 2009 [3] Mitra, N. J., Flury, S., Ovsjanikov, M., Gelfand, N., Guibas, L. J., and Pottmann. Dynamic Geometry Registration. SGP 2007. [4] Wand, M., Jenke, P., Huang, Q., Bokeloh, M., Guibas, L. J., and Schilling, A. Reconstruction of Deforming Geometry from Time-varying Point Clouds. SGP 2007. [5] Nehab, D., Rusinkiewicz, S., Davis, J., Ramamoorthi, R. Efficiently Combining Positions and Normals for Precise 3D Geometry. SIGGRAPH 2005 [6] Sharf, A., Alcantara, D., Lewiner, T., Greif, C., Sheffer, A., Amenta, N., and Cohen-Or, D. Space-time Surface Reconstruction Using Incompressible Flow. SIGGRAPH Asia 2008. [7] Vlasic, D., Peers, P., Baran, I., Debevec, P., Popovic, J., Rusinkiewicz, S., and Matusik, W. Dynamic Shape Capture Using Multi- view Photometric Stereo. SIGGRAPH Asia 2009. [8] Li, H., Adams, B., Guibas, L. J., and Pauly, M. Robust Single-view Geometry and Motion Reconstruction. SIGGRAPH Asia 2009. [9] Chang, W., Zwicker, M. Automatic Registration for Articulated Shapes. SGP 2008. [10] Huang, Q., Adams, B., Wicke, M., and Guibas, L. J. Non-Rigid Registration Under Isometric Deformations. SGP 2008. BOOK: Emanuele Trucco and Alessandro Verri. Introductory Techniques for 3-D Computer Vision. Prentice Hall 1998.

1 0

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