- talks - lists.cs.princeton.edu

C Toler-Franklin general exam
by Melissa M Lawson 15 May '07

15 May '07

Corey Toler-Franklin will present her research seminar/general exam on Monday May 21 at 2PM in Room 402. The members of her committee are: Szymon Rusinkiewicz (advisor), Adam Finkelstein, and Tom Funkhouser. 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. ------------------------------------------- Illustration of Complex Real-World Objects using Images with Normals Corey Toler-Franklin This project investigates the creation of non-photorealistic illustrations from a type of data lying between simple 2D images and full 3D models: images with both a color (albedo) and a surface normal stored at each pixel. Images with normals combine an acquisition process only mildly more complex than that for digital photographs (and significantly easier than 3D scanning) with the power and flexibility of tools similar to those originally developed for full 3D models. We investigate methods for signal processing on images with normals, developing algorithms for scale-space analysis, and segmentation. These are used to implement analogues of stylized rendering techniques including toon shading, line drawing and and exaggerated shading. We believe that images with normals or "RGBN images" may become an important and widely-used data type, because of the ease, flexibility, and quality with which they may be acquired, and because they contain enough information to permit sophisticated analysis and depiction.We show that our rendering pipeline can produce detailed yet understandable illustrations in medical, technical, and archaeological domains. Books WATT, A. 1996. 3D Computer Graphics Second Edition. WATT, A., AND WATT, M. 1998 Advanced Animation and Rendering Techniques. Papers DECARLO, D., FINKELSTEIN, A., RUSINKIEWICZ, S., AND SAN- TELLA, A. 2003. Suggestive Contours for Conveying Shape. ACM Trans. Graphics (Proc. SIGGRAPH), Vol. 22, No. 3, 848-855. DECARLO, D., FINKELSTEIN, A., AND RUSINKIEWICZ, S. 2004. In- teractive Rendering of Suggestive Contours with Temporal Coherence. In Proc. NPAR. DECAUDIN, P. 1996. Cartoon-Looking Rendering of 3D-Scenes. Tech. Rep. 2919, INRIA. FELZENSZWALB, P., AND HUTTENLOCHER, D. 2004. Efficient Graph- Based Image Segmentation. International Journal of Computer Vision, Vol. 59, No. 2 (Sept.). GOOCH, A., GOOCH, B., SHIRLEY, P., AND COHEN, E. 1998. A Non- Photorealistic Lighting Model for Automatic Technical Illustration. In Proc. ACM SIGGRAPH. LUFT, T., COLDITZ, C., AND DEUSSEN, O. 2006. Image Enhancement by Unsharp Masking the Depth Buffer. ACM Trans. Graphics (Proc. SIGGRAPH), Vol. 25, No. 3. MARKOSIAN, L., KOWALSKI, M., TRYCHIN, S., BOURDEV, L., GOLDSTEIN, D., AND HUGHES, J. 1997. Real-Time Nonphotore- alistic Rendering. In Proc. ACM SIGGRAPH, 415-420. RASKAR , R., TAN, K.-H., FERIS, R., YU, J., AND TURK, M. 2004. Non-Photorealistic Camera: Depth Edge Detection and Stylized Ren- dering using Multi-Flash Imaging. ACM Trans. Graphics (Proc. SIG- GRAPH), Vol. 23, No. 3. RUSHMEIER, H., TAUBIN, G., AND GUEZIEC, A. 1997. Applying Shape From Lighting Variation to Bump Map Capture. In Proc. Eurographics Rendering Workshop. RUSINKIEWICZ, S., BURNS, M., AND DECARLO, D. 2006. Exagger- ated Shading for Depicting Shape and Detail. ACM Trans. Graphics (Proc. SIGGRAPH), Vol. 25, No. 3. SAITO, T., AND TAKAHASHI, T. 1990. Comprehensible Rendering of 3-D Shapes. In Proc. ACM SIGGRAPH, 197-206. SLOAN, P.-P., MARTIN, W., GOOCH, A., AND GOOCH, B. 2001. The Lit Sphere: A Model for Capturing NPR Shading from Art. In Proc. Graphics Interface. THIRION, J.-P., AND GOURDON, A. 1996. The 3D Marching Lines Algorithm. Graphical Models and Image Processing, Vol. 58, No. 6 (Nov.), 503-509. TOMASI, C., AND MANDUCHI, R. 1998. Bilateral Filtering for Gray and Color Images. In Proc. ICCV. WINKENBACH, G., AND SALESIN, D. 1994. Computer-Generated Pen- and-Ink Illustration. In Proc. SIGGRAPH.

1 0

J Yoon general exam
by Melissa M Lawson 14 May '07

14 May '07

Janet Yoon will present her research seminar/general exam on Thursday May 17 at 10AM in Room 402. The members of her committee are Bob Tarjan (advisor), Andrea LaPaugh, and Bob Sedgewick. 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. ---------------------------------------------------- Planarity testing is used for many real-world applications such as circuit design. The first linear time planar embedding algorithm was introduced in 1974 by Hopcroft and Tarjan. More than thirty years later there continues to be an interest in this area. Efficiency is an important factor in the applicability of an algorithm, but just as crucial is its simplicity. I will first briefly introduce past algorithms; more specifically the algorithms of Cederbaum Even and Lempel, Boothe and Lueker, and Boyer and Mervold. Then I will introduce a better abstracted, simpler algorithm based on these algorithms. References [1] K. S. Booth and G. S. Lueker. Testing the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Com-put. Syst. Sci., 13:335-379, 1976. [2] J. M. Boyer and W. Myrvold. Stop minding your p's and q's: A simplified o(n) planar embedding algorithm. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, volume 13, pages 140-146, 1999. [3] Z. Galil, G. F. Italiano, and N. Sarnak. Fully dynamic planarity testing. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4, Victoria, B.C., Canada., pages 495-506, New York, 1992. ACM. [4] J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM 21,pages 549-558, Oct. 1976. [5] W-L Hsu. An efficient implementation of the pc-tree algorithm of shih and hsu's planarity test. Tech. Report, Inst of Inf Science,Academia Sinica, 1993. [6] J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005. [7] A. Lempel, A. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of Graphs: International Symposium, Rome, Italy., pages 215{232, New York, 1967. Gordon and Breach. [8] R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs.SIAM J. Appl. Math., 36:177-189, 1979. [9] R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980. [10] Y. Makarychev. A short proof of kuratowski's graph planarity criterion. Journal of Graph Theory, 25:129-131, 1997. [11] J. M. Boyer P. F. Cortese M. Patrignani and G. Di Battista. Stop minding your p's and q's: Implementing a fast and simple dfs-based planarity testing and embedding algorithm. 2003. [12] W.-K. Shih and W.-L. Hsu. A new planarity test. Theoretical Computer Science, pages 179-191, 1999. [13] R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J.Comput., 1(2):146-160, 1972. [14] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1987. [15] R. M. McConnell W.-L. Hsu. Pq trees, pc trees, and planar graphs. Theoretical Computer Science, 296(1):59-74, 2003. [16] S. G. Williamson. Depth-first search and kurotowski subgraphs. Journal of the ACM, 31(4):681-693, 1984.

1 0

Q Xi generals - canceled today
by Melissa M Lawson 14 May '07

14 May '07

Due to a scheduling conflict, Qian's generals will not be held today. We will reschedule and reannounce. thanks.

1 0

N Heninger general exam
by Melissa M Lawson 11 May '07

11 May '07

Nadia Heninger will present her research seminar/general exam on Thursday May 17 at 2PM in Room 402. The members of her committee are; Bernard Chazelle (advisor), Boaz Barak, and Moses Charikar. 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: In 2004, Goemans and Vondrak showed that there is a sparse set of edges which covers the minimum spanning tree of a random subgraph of vertices or edges chosen independently with probability p. I improve the bounds for the case where edges can be chosen with arbitrary different probabilities and show that this result does not generalize to the case when vertices are chosen non-independently. I will also explain how their main lemma is actually an intriguing fact about reliability polynomials, which represent the probability that a network is connected under failure, a well-known #P-complete problem. I will discuss some natural open problems connected to this work. Reading list: N. Ailon, B. Chazelle, S. Comandur, and D. Liu Self-Improving Algorithms. SODA 2006 Holm, J., de Lichtenberg, K., and Thorup, M. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. STOC '98. Charikar, M. S. Similarity estimation techniques from rounding algorithms. STOC '02. Indyk, P. 2006. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53, 3 (May. 2006), 307-323. M. Luby and A. Wigderson, "Pairwise independence and derandomization," Tech. Rep. 95-035, International Computer Science Institute (ICSI), Berkeley, 1995. A. Z. Broder, M. Charikar, A. Frieze, and M. Mitzenmacher. Min-wise independent permutations. STOC '98 S. Albers and J. Westbrook. Self-organizing data structures. In Online Algorithms: The State of the Art, Fiat-Woeginger, Springer, 1998. Motwani & Raghavan Randomized Algorithms Ch 5, 6, 8, 10 Mitzenmacher & Upfal Probability and Computing Ch 2, 3, 4, 5, 6, 7, 9 Vazirani Approximation Algorithms Ch 12, 13, 14, 15

1 0

A Halderman preFPO
by Melissa M Lawson 11 May '07

11 May '07

Alex Halderman will present his preFPO on Thursday, May 17 at 10 A.M. in CS 302. The members of his committee are: Ed Felten, advisor; Andrew Appel and Avi Rubin (Johns Hopkins), readers; Adam Finkelstein and Brian Kernighan, non-readers. Everyone is invited to attend his talk. The abstract follows below. ------------- Learning from Security Failures in Non-Traditional Computing Environments Decades of bitter experience with security failures in desktop computers and network environments have led to intuitions and engineering practices that help us build more robust systems. However, as computers are becoming smaller and cheaper, they are taking on new forms that challenge our intuitions. >From RFID tags embedded in sneakers and passports, to "smart" cell phones and car navigation systems, many new applications occupy environments that look little like those with which researchers are familiar, and the old rules increasingly do not apply. When security fails in such environments, it often fails spectacularly, with layers of vulnerabilities that, compounded, are costly or impossible to repair. By studying such security disasters, and asking why they are especially severe, we hope to develop new security techniques suitable for a world of ubiquitous computing. One traditional security intuition that is now being challenged is the distinction between data and software. When received from a trusted source, data files are considered a lower risk than software, since only software can contain security bugs that weaken the computer's defenses. Recent events cause us to question the value of this distinction. In a widely-publicized incident, the record label Sony-BMG sold several million music CDs (normally considered a data-only medium) that contained undisclosed software intended to thwart copying. We studied this software using a variety of analytical techniques and discovered that it contained serious defects that threatened consumers' security and privacy. Merely playing the CDs caused the installation of dangerous software that provided several routes for attackers to subvert the computer's security mechanisms. These problems were exacerbated by the non-traditional environment of a hybrid music and software CD, which allowed the discs to avoid scrutiny by the ecosystem of security software vendors that monitor for deviant behavior. Other security intuitions are being challenged in the realm of embedded computers. Once, such systems were though of as "dumb" appliances, protected from most security risks by their simple designs and lack of network connectivity, but as they have grown increasingly sophisticated, they have come to resemble full-blown computers, together with the attendant security problems. We found evidence of this trend in the United States' most widely used electronic voting machine, the Diebold AccuVote-TS. Using reverse-engineering and novel software analysis methods, we discovered that the machine suffers from many of the same security problems as desktop PCs, including the potential for attackers to install malicious software and spread viruses from machine to machine. Because of its embedded nature, the machine has none of the protections that are now standard on desktop computers. As a result, an attacker could exploit these problems to steal votes undetectably on a wide scale. In many ways, our approach to these and other examples can be compared to the systematic disaster investigations conducted after major transportation accidents or structural failures. We seek to learn what went wrong not only in each particular case but also in the broader context that allowed the problems to occur. Our findings highlight the need to extend existing protections to non-traditional environments, as well as to develop new security techniques that are suitable to these applications. We propose specific remedies in each case, such as cryptographic privacy protection protocols for camera phones, and efficient machine-assisted auditing techniques for voting. We also apply our theories to predict problems that may be discovered in the future: for instance, Internet worms that spread by exploiting weaknesses in the new generation of networked videogame consoles. Finally, we consider legislative and regulatory remedies, including policy measures that have already gained momentum in the wake of our findings concerning the Sony-BMG and Diebold systems.

1 0

Y Zhu general exam
by Melissa M Lawson 10 May '07

10 May '07

Yaping Zhu will present her research seminar/general exam on Wednesday May 16 at 10AM in Room 402. The members of her committee are Jennifer Rexford (advisor), Larry Peterson, and Vivek Pai. Everyone is invited to attend her talk, and those faculty members wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ---------------------------------- Abstract Conventional wisdom has held that routing protocols can not achieve both scalability and high availability. Despite scaling rather well, today's Internet routing system does not react quickly to changing network conditions. Overlay networks, on the other hand, can respond quickly to changing network conditions, but their reliance on aggressive probing does not scale to large topologies. This project presents a resilient layered routing architecture called UFO (Underlay Friendly to Overlays), which achieves the best of both worlds by providing router support for overlay routing mechanisms. UFO comprises two changes to existing routers: (i) data-plane support for deflection packets at the behest of the overlay and (ii) explicit notification about significant changes in network conditions. We present these two mechanisms, and demonstrate how they facilitate the scalable deployment of overlay routing mechanisms at the network layer. Prototype is implemented based on PL-VINI platform, with preliminary evaluation results. Reading List 1. L.Peterson and B.Davie, "Computer Networks: A Systems Approach", 3rd Edition. 2. D.Clark, "Design Philosophy of the DARPA Internet Protocols", in Proc. ACM SIGCOMM, Aug 1988. 3. J.Saltzer, D.Reed and D.Clark, "End-to-End Arguments in System Design", ACM Transactions on Computer Systems, Nov 1984. 4. A.Bavier, N.Feamster, M.Huang, L.Peterson, and J.Rexford, "In VINI Veritas: Realistic and Controlled Network Experimentation", in Proc. ACM SIGCOMM, Sep 2006. 5. D.Andersen, H.Balakrishnan, M.Kaashoek, and R.Morris, "Resilient Overlay Networks", in Proc. ACM SOSP, Oct 2001. 6. N.Feamster, D.Andersen, H.Balakrishnan, and F.Kaashoek, "Measuring the Effects of Internet Path Faults on Reactive Routing", in Proc. ACM SIGMETRECS, Jun 2003. 7. A.Nakao, L.Peterson, and A.Bavier, "A Routing Underlay for Overlay Networks", in Proc. ACM SIGCOMM, Aug 2003. 8. J.Jannotti, "Network Layer Support for Overlay Networks", in Proc. IEEE OPENARCH, 2002 9. T.Griffin, F.Shepherd, and G.Wilfong, "The Stable Paths Problem and Interdomain Routing", IEEE Transactions on Networking. Volume10, Issue2 p232-243. 10. R.Morris, E.Kohler, J.Jannotti, and M.Kaashoek, "The Click Modular Router", in Proc. ACM SOSP, Dec 1999.

1 0

Yi Wang general exam
by Melissa M Lawson 10 May '07

10 May '07

Yi Wang will present his research seminar/general exam on Wednesday May 16 at 2PM in Room 402. The members of his committee are Jennifer Rexford (advisor), Larry Peterson, and Kai Li. 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. ---------------------------------- Morpheus: Making Routing Programmable Abstract: The Border Gateway Protocol (BGP) is used by Internet Service Providers (ISPs) to exchange reachability information with neighboring domains. Internet Service Providers (ISPs) express complex policies, affecting everything from business relationships with their neighbors to traffic engineering, scalability, and security, by configuring the BGP. However, the routing architecture within an ISP, coupled with the multi-step BGP route-selection algorithm running on the routers, imposes significant restrictions on the policies that can be realized in practice. These restrictions stand in the way of ISPs achieving policy objectives that are important in practice, such as enabling new services to customers. We argue that the limitations of BGP can be overcome by providing greater visibility into the candidate routes, a more flexible decision process, and support for for multipath routing and forwarding. We present Morpheus, a modular, open routing platform that enables network operators to realize many useful policies that are infeasible today through: (1) flexible composition of multiple (possibly third-party developed) policy modules, and (2) programming the route-selection algorithms. Morpheus also supports multipath routing, which is essential in enabling many new customizable routing services. Morpheus can be readily deployed without requiring changes in other domains. We've implemented an Morpheus prototype as an extension to XORP, the extensible open routing platform. Our evaluation of the prototype demonstrates that the system can scale to the large number of address blocks and BGP sessions present in large backbone networks. We are currently working on demonstrating the flexibility of the prototype in supporting new routing policies. Reading list: Textbook: L. Peterson and B. Davie, Computer Networks: A Systems Approach, Morgan Haulmann, 3e, 2003 Papers: [1] D. Clark, " <http://www.cs.utah.edu/classes/cs7941-001/papers/e2e88.pdf> The Design Philosophy of the DARPA Internet Protocols," ACM SIGCOMM, August 1988 [2] N. Feamster, H. Balakrishnan, J. Rexford, A. Shaikh, and J. van der Merwe, " <http://www.cs.princeton.edu/%7Ejrex/papers/rcp.pdf> The Case for Separating Routing from Routers," ACM SIGCOMM workshop on Future Directions in Network Architecture, August 2004 [3] A. Greenberg, G. Hjalmtysson, D. Maltz, A. Meyers, J. Rexford, G. Xie, H. Yan, J. Zhan, and H. Zhang, " <http://www.cs.princeton.edu/%7Ejrex/papers/ccr05-4d.pdf> A Clean Slate 4D Approach to NetworkControl and Management," ACM SIGCOMM Computer Communications Review, October 2005 [4] M. Handley, E. Kohler, A. Ghosh, O. Hodson, P. Radoslavov, " <http://www.xorp.org/papers/xorp-nsdi.pdf> Designing Extensible IP Router Software," USENIX Symposium on Networked Systems Design and Implementation, May 2005 [5] Matthew Caesar, Donald Caldwell, Nick Feamster, Jennifer Rexford, Aman Shaikh, and Jacobus van der Merwe, " <http://www.cs.princeton.edu/%7Ejrex/papers/rcp-nsdi.pdf> Design and implementation of a Routing Control Platform," USENIX Symposium on Networked Systems Design and Implementation, May 2005 [6] B. Raghavan and A. Snoeren, " <http://www.cs.ucsd.edu/%7Ebraghava/papers/platypus-sigcomm04.pdf> A System for Authenticated Policy-Compliant Routing," ACM SIGCOMM, September 2004 [7] T. V. Lakshman, T. Nandagopal, R. Ramjee, K. Sabnani, and T. Woo, " <http://www.sigcomm.org/HotNets-III/HotNets-III%20Proceedings/lakshman.pdf> The SoftRouter Architecture," ACM Workshop on Hot Topics in Networks, November 2004 [8] G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. McDaniel, and A. Rubin, " <http://www.isoc.org/isoc/conferences/ndss/03/proceedings/papers/5.pdf> Working Around BGP: An Incremental Approach to Improving Security and Accuracy for Interdomain Routing," Symposium on Network and Distributed System Security, February, 2003 [9] T. Griffin, B. Shepherd, and G. Wilfong, " <http://www.stanford.edu/%7Erjohari/336/Griffin_SPP.pdf> The Stable Paths Problem and Interdomain Routing," IEEE Transactions on Networking, 10(2), April 2002 [10] M. Caesar and J. Rexford, " <http://www.cs.princeton.edu/%7Ejrex/papers/policies.pdf> BGP Routing Policies in ISP Networks," IEEE Network Magazine, Special Issue on Interdomain Routing, November/December 2005 [11] Hong Yan, T. S. Eugene Ng, David Maltz, Hui Zhang, Hemant Gogineni and Zheng Cai, " <http://www.cs.rice.edu/%7Eeugeneng/papers/NSDI07-4D.pdf> Tesseract: A 4D Network Control Plane", USENIX Symposium on Networked Systems Design & Implementation, April 2007 [12] Wen Xu and Jennifer Rexford, " <http://www.cs.princeton.edu/%7Ejrex/papers/multipath06.pdf> MIRO: Multi-path Interdomain ROuting," ACM SIGCOMM, September 2006

1 0

JiMin Song general exam
by Melissa M Lawson 10 May '07

10 May '07

JiMin's exam is at 10AM this morning. It was not mentioned in the talk announcement. Sorry!

1 0

C Kim general exam
by Melissa M Lawson 10 May '07

10 May '07

Chang Kim will present his research seminar/general exam on Tuesday May 15 at 10AM in Room 402. The members of his committee are Jennifer Rexford (advisor), Margaret Martonosi, and David August. 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. ---------------------------------- SEIZE: Scalable and Efficient Zero-configuration Enterprise Architecture Abstract Most conventional enterprise or campus networks consist of Ethernet-based IP subnets interconnected by routers. Although each subnet runs with minimal (or zero) configuration by virtue of Ethernet's flat-addressing and self-learning capability, interconnecting subnets at the IP-level introduces a significant amount of configuration and management overhead on both end-hosts and routers. The configuration problem becomes more serious as an enterprise network grows by merging multiple remote sites or by supporting a large number of mobile end-hosts. Deploying enterprise-wide Ethernet, however, cannot solve this problem because Ethernet bridging does not scale. As an alternative, we propose a scalable and efficient zero-configuration architecture (SEIZE) for enterprise networks. SEIZE provides "plug-and-play" capability via flat addressing and yet allows for scalability and efficiency through a combination of shortest-path routing and hash-based location resolution. Networking nodes perform location resolution on an on-demand basis and can cache the results to optimize routing paths and to avoid redundant resolution as well. We implemented a SEIZE prototype system using a collection of Click modular router elements and the XORP routing protocol daemon. For evaluation, we run the system on Emulab with real enterprise traffic traces. Our experiments show that SEIZE exhibits near-optimal path efficiency, while limiting the number of host information entries replicated over a network and reducing the control overhead as much as two orders of magnitude compared with the conventional Ethernet bridging. Papers 1. L. Kleinrock, and F. Kamoun, "Hierarchical Routing for Large Networks; Performance Evaluation and Optimization," Computer Networks vol. 1, 1977. 2. R. Perlman, " An Algorithm for Distributed Computation of a Spanning Tree in <http://www1.cs.columbia.edu/%7Eji/F02/ir02/p44-perlman.pdf> an Extended LAN," Proc. ninth Data Communications Symposium, 1985. 3. D. Peleg, and E. Upfal, " A Trade-Off between Space and Efficiency for Routing <http://portal.acm.org/ft_gateway.cfm?id=62217&type=pdf&coll=GUIDE&dl=GUIDE&… CFTOKEN=37897046> Tables," Journal of the ACM, 1989. 4. T. Rodeheffer, C. Thekkath, and D. Anderson, "SmartBridge: A scalable bridge architecture <http://www.sigcomm.org/sigcomm2000/conf/paper/sigcomm2000-6-2.pdf> ," Proc. ACM SIGCOMM, 2000. 5. Andy Myers, T. S. Eugene Ng, and H. Zhang, "Rethinking the Service Model: Scaling Ethernet to a Million <http://www.cs.cmu.edu/%7Eacm/papers/myers-hotnetsIII.pdf> Nodes," Proc. of HotNets-III, 2004. 6. R. Perlman, " <http://www.ieee-infocom.org/2004/Papers/26_1.PDF> Rbridges: Transparent routing," Proc. of IEEE Infocom, 2004. 7. S. Sharma, K. Gopalan, S. Nanda, and T. Chiueh, "Viking: <http://www.ieee-infocom.org/2004/Papers/47_3.PDF> A multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," Proc. of IEEE Infocom, 2004. 8. D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, " Consistent hashing and random trees: distributed caching <http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTr… CachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf> protocol for relieving hot spots on the World Wide Web," Proc. ACM STOC, 1997. 9. J. Eriksson, M. Faloutsos, and S. Krishnamurthy, "PeerNet: Pushing Peer-to-Peer Down the Stack <http://iptps03.cs.berkeley.edu/final-papers/peernet.pdf> ," Proc. of International Workshop on Peer-to-Peer Systems, 2003. 10. D. Clark, R. Braden, A. Falk, and V. Pingali, "FARA: Reorganizing the addressing architecture <http://www.isi.edu/newarch/DOCUMENTS/FARA.FDNA03.pdf> ," Proc. of ACM SIGCOMM Workshop on Future Directions in Network Architecture, 2003. 11. M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, I. Stoica, and S. Shenker, "ROFL: Routing on Flat Labels <http://project-iris.net/irisbib/papers/flatlabels:sigcomm2006/paper.pdf> ," Proc. of ACM SIGCOMM, 2006. 12. M. Caesar, M. Castro, E. Nightingale, Gerg O, and A. Rowstron, "Virtual Ring Routing: Network Routing Inspired by <http://www.sigcomm.org/sigcomm2006/discussion/getpaper.php?paper_id=33> DHTs," Proc. of ACM SIGCOMM, 2006. Textbooks 1. L. Peterson, and B. Davie, Computer Networks: A Systems Approach, Morgan Kaufmann, 3e, 2003 2. R. Perlman, Interconnections: Bridges, Routers, Switches, and Internetworking Protocols, Addison-Wesley, 2e, 1999

1 0

J Song general exam
by Melissa M Lawson 10 May '07

10 May '07

JiMin Song will present her research seminar/general exam on Thursday May 10 in Room 302 (note room!). The members of her committee are: Mona Singh (advisor), Olga Troyanskaya, and Tom Funkhouser. 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 Protein interactions play a key role in almost all biological processes. Recently, high-throughput experiments have uncovered large networks of protein-protein interactions for several species, including human, fruit fly and yeast. It has been postulated that analysis of these protein interaction maps should provide hints to the cell's higher-level organization, and help uncover protein functions, complexes and pathways. A protein-protein interaction network is considered as an undirected graph such that nodes are proteins and edges are interactions between two proteins. Graph clustering methods provide one way for analyzing these networks in order to uncover functional modules and protein complexes. I introduce an evaluation framework for analyzing graph clustering methods. I consider six different evaluation measures, taking into account biological process, cellular component, and protein complex annotations, to compare four diverse graph clustering algorithms. I selected four graph clustering methods, a spectral clustering method, a Markov clustering method, a density-periphery based clustering method, and a clique-finding clustering method. I find that the clique-finding clustering method consistently out performs the others, suggesting that future research along these lines should focus on methods with similar properties. Reading list Textbook: Bioinformatics by Mount - Chapters: 3, 4, 5, 7, 10. Papers: - E Alm and AP Arkin, Biological networks, Curr. Opin. Struct. Biol 2003 - LH Hartwell et al, From molecular to modular cell biology, Nature 1999 - Spirin and Mirny, Protein complexes and functional modules in molecular networks, PNAS 2003 - Sharan et al, Network-based prediction of protein function, EMBO 2007 - Newman, Modularity and community structure in networks, PNAS 2006 - Enright et al, An efficient algorithm for large-scale detection of protein families, NAR 2002 - Altaf-Ul-Amin, Development and implementation of an algorithm for detection of protein complexes in large interaction networks, BMC Bioinformatics 2006 - Palla et al, Uncovering the overlapping community structure of complex networks in nature and society, Nature 2005 - Brohee and van Helden, Evaluation of clustering algorithms for protein-protein interaction networks, BMC Bioinformatics 2006

2 1