- talks - lists.cs.princeton.edu

E Nabieva FPO
by Melissa M Lawson 16 Aug '07

16 Aug '07

Elena Nabieva will present her FPO on Thursday August 23 at 3PM in room 402. The members of her committee are Mona Singh, advisor; Bernard Chazelle and Olga Troyanskaya, readers; Szymon Rusinkiewicz and Ned Wingreen (MolBio). A copy of her thesis, "Topology and Function in Protein Interaction Networks" is on display in Room 310. Everyone is invited to attend her talk.

1 0

D Dantas FPO
by Melissa M Lawson 16 Aug '07

16 Aug '07

Daniel Dantas will present his FPO on Wednesday August 22 at 2PM in Room 402. The members of his committee are David Walker, advisor; Andrew Appel and Stephanie Weirich (U Penn), readers; Ed Felten and David August, nonreaders. A copy of is thesis, "Analyzing Security Advice in Functional Aspect-oriented Programming Languages" is on display in Room 310. Everyone is invited to attend his talk.

1 0

M Bridges preFPO
by Melissa M Lawson 07 Aug '07

07 Aug '07

Matt Bridges will present his preFPO on Monday August 13 at 2PM in Room 402. The members of his committee are: David August, advisor; Kai Li and Dan Lavery (Intel), readers; Margaret Martonosi (ELE) and Doug Clark, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------ Title: Unlocking the Potential of Automatic Parallelization Abstract: Multiprocessor systems, particularly chip multiprocessors, have emerged as the predominant organization for future microprocessors. Systems with 4 cores are already shipping and a future with 32 or more cores is easily conceivable. Unfortunately, multiple cores do not directly result in improved application performance, particularly for legacy applications. Consequently, parallelizing applications to execute on multiple cores is essential. Parallel programming models and languages could be used to create multithreaded applications. However, moving to a parallel programming model only increases the complexity and cost involved in software development. To address these costs, automatic thread extraction techniques, such as TLS and DSWP, have been explored. Unfortunately, the amount of parallelism that has been automatically extracted is generally insufficient to keep many cores busy. First, many important loops are not parallelized because the compiler lacks the necessary scope to apply the optimization. Second, the sequential programming model forces programmers to define a single legal application outcome, rather than allowing for a range of legal outcomes, leading to conservative dependences that prevent parallelization. This dissertation explores the performance of key existing, state-of-the-art methodologies in automatic thread extraction. The potential of these methodologies is significantly increased by combining them with an expanded optimization scope, which facilitates the optimization of large loops, leading to parallelism at higher levels in the application. Finally, natural, simple extensions to the sequential programming model are presented to break the limitations which can prevent the extraction of scalable parallelism. Through a case study of several applications, including all C benchmarks in the SPEC CINT2000 suite, this dissertation shows how scalable parallelism can be extracted. For the SPEC CINT2000 suite, our experience demonstrates that, by changing only 56 source code lines, all of the applications were parallelizable by automatic thread extraction. This process, constrained by the limits of modern optimizing compilers, yielded a speedup of 540%.

1 0

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