- talks - lists.cs.princeton.edu

M Hibbs preFPO
by Melissa M Lawson 03 Aug '07

03 Aug '07

Matt Hibbs will present his preFPO on Friday August 10 at 10AM in Carl Icahn Labs Room 200 (CIL 200). The members of his committee are: Olga Troyanskaya, advisor; Kai Li and Tom Funkhouser, readers; David Botstein (MOL/Genomics) and Leonid Kruglyak (EEB/Genomics), nonreaders. Everyone is invited to attend his talk. His title and abstract follow below. ------------------------------------- Title: Analysis and Visualization of Large-Scale Gene Expression Microarray Compendia Over the past decade, gene expression microarray data has become one of the most important tools available for biologists to understand molecular processes and mechanisms on the whole-genome scale. Microarray data provides a window into the inner workings of the transcriptional process that is vital for cellular maintenance, development, biological regulation, and disease progression. While an exponentially increasing amount of microarray data is being generated for a wide variety of organisms, there is a severe lack of methods designed to utilize the vast amount of data currently available. In my work, I explore several techniques to meaningfully harness large-scale collections of microarray data both to provide biologists with a greater ability to explore data repositories, and to computationally utilize these repositories to discover novel biology. First, I will discuss techniques for visualization-based analysis of microarray data on the scale of individual datasets. These techniques include incorporating statistical measures into visualization schemes and utilizing alternative views of data to gain a broader picture. Second, I will focus on novel methods that allow users to simultaneously view multiple datasets with the goal of providing a larger context within which to understand individual datasets. These techniques include developing multi-dataset visualization methods as well as utilizing new technologies such as very large format display devices. Third, effective search and analysis techniques are required to guide researchers and enable their effective use of large-scale repositories. I will present a user-driven search algorithm designed to both quickly locate relevant datasets in a collection and to then identify novel players related to the user's query. This technique is useful as an independent search/exploration method, can be incorporated into visualization systems, and can be used to predict novel functions for genes. I will discuss how we have successfully used this approach to discover novel biology, including directing a large-scale experimental investigation of S. cerevisiae mitochondrial organization. The combination of visualization-based analysis methods and exploratory algorithms such as those presented are vital to future systems biology research. As data collections continue to grow and as new forms of data are generated, it will become increasingly important to develop methods and techniques that will allow experts to intelligently sift through the available information to make new discoveries.

1 0

Yong Wang FPO
by Melissa M Lawson 31 Jul '07

31 Jul '07

Yong Wang will present his FPO on Monday August 6 at 2PM in Room 402. The members of his committee are: Margaret Martonosi (EE), advisor; Jennifer Rexford and Li-Shiuan Peh (EE), readers; Kai Li and Larry Peterson, nonreaders. A copy of his thesis, "Situation-Aware Optimizations in Challenged Networks", is on display in Room 310. Everyone is invited to attend his talk.

1 0

M McCann FPO
by Melissa M Lawson 11 Jun '07

11 Jun '07

Mark McCann will present his FPO on Tuesday June 19 at 3:30 PM in Room 402. The members of his committee are Nick Pippenger, advisor; Bernard Chazelle and Ken Steiglitz, readers; Bob Tarjan and Moses Charikar, nonreaders. A copy of his thesis, "Memory in Media with Manufacturing Faults" is on display in Room 310. Everyone is invited to attend his talk.

1 0

M Mahmoody Ghidary general exam
by Melissa M Lawson 17 May '07

17 May '07

Mohammad Mahmoody Ghidary will present his research seminar/general exam on Thursday May 24 at 2PM in Room 402. The members of his committee are: Boaz Barak (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. ---------------------- Abstract: ----------------------------------- I will show the first lower-bound on the efficiency of Signature Schemes in the random oracle Model. The lower-bound is tight up to a constant factor for one-time signatures. The current constructions of signatures are considered to be inefficient by practitioners, and the result shows that it is actually inherent. We will see some ideas of the proof. No background is assumed. Reading List: ----------------------------------- The list contains also some papers about another research direction: "Average-case vs Worst-case complexity". General Complexity Theory: The book: "Complexity Theory: A Modern Approach" (by Arora, Bara) Chapters 1 to 9 Advanced Complexity topics: The same book. Chapters: 16: Derandomization, Expanders and Extractors 17: Hardness amplification and error correcting codes 18: PCP and hardness of approximation. General Cryptography: Lecture notes of the Cryptography course by Barak available at: http://www.cs.princeton.edu/courses/archive/fall05/cos433/ Lectures 1-20 Research Papers: --Worst-Case vs Average-Case Complexity: *Feigenbaum, Fortnow. On the random-self-reducibility of complete sets. *Bogdanov, Trevisan. "On worst-case to average-case reductions for NP problems" *Gutfreund, Shaltiel, Ta-Shma. "If NP languages are hard on the worst-case then it is easy to find their hard instances." --The possibility and the efficiency of cryptographic reductions: *R. Impagliazzo and S. Rudich, "Limits on the Provable Consequences of One-Way Permutations" *Reingold, Trevisan, Vadhan "Notions of Reducibility between Cryptographic Primitives" *Katz, Gennaro, Gertner, "Lower Bounds on the Efficiency of Encryption and Digital Signature Schemes" *Gennaro, Trevisan, "Bounds on the Efficiency of Generic Cryptographic Constructions"

1 0

S Brahma general exam
by Melissa M Lawson 17 May '07

17 May '07

Siddhartha Brahma will present his research seminar/general exam on Wednesday May 23 at 10AM in Room 402. The members of his committee are Bob Tarjan (advisor), Moses Charikar, and Boaz Barak. 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: Studies in Distribution Sensitive Data Structures A distribution senstitve data structure is one whose running time on a sequence of operations supported by the data structure depends on some distributional properties of the sequence. Although some work had been done before, distribution sensitive data structures became important after the seminal paper on Splay trees by Sleator and Tarjan [0]. In the paper several types of distributive properties were defined and it was proved that splay trees have several of these properties (eg. static optimality, working set property, dynamic finger property, etc) by using amortized analysis, and miraculously without storing any extra information about the sequence. Then the question naturally arises whether we can define similar properties for data structures other than binary search trees. There has been interesting work recently in terms of both defining new properties (unified property) and proving these properties for new or existing data stuctures (eg. planar point location data sturctures, priority queues, etc). We will give a broad survey of the whole area, mentioning some recent results in detail and discuss some interesting open problems. We will also show some preliminary results for data structures for the Max Priority Interval problem having some of the properties described above. Reading List: [0] D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. J.ACM, 1985. [1] John Iacono. Distribution Sensitive Data Structures. Ph.D. Thesis. Rutgers, SUNY,2001. [2] Chengwen Chris Wang. Multi-Splay Trees. PhD thesis, CMU, Pittsburg, PA, 2006. [3] Introduction to Algorithms. Cormen, Leiserson, Rivest and Stein, MIT Press, 2001.(Chapters 10-14, 17, 18-21). [5] J.Iacono and S.Langerman. Proximate planar point location. in SoCG 2003. [6] R. E. Tarjan. Amortized computational complexity. SIAM J. Appl. Discrete Meth., 1983. [6] Dion Harmon. New Bounds on Optimal Binary Search Trees. PhD thesis, MIT, Boston, MA, 2006. [7] M. T. Goodrich, M. Orletsky, K. Ramaiyer, Methods for achieving fast query times in point location data structures, in SODA 1997. [8] Data Structures and Network Algorithms. Robert E. Tarjan, 1983. [9] John Iacono: Optimal planar point location. SODA 2001. [10] Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu: Dynamic Optimality -- Almost. FOCS 2004. [11] C.C.Wang, J.Derryberry, D.D.Sleator: O(\log\log n)-competitive dynamic binary search trees. SODA 2006.

1 0

Q Xi general exam - rescheduled
by Melissa M Lawson 15 May '07

15 May '07

Qian Xi's general exam has been rescheduled for this Wednesday May 16 at 4PM in Room 402. Her committee is JP Singh (advisor), David August, and Vivek Pai.

1 0

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