- talks - lists.cs.princeton.edu

X Chen general exam
by Melissa Lawson 14 May '09

14 May '09

Xiaobai Chen will present his research seminar/general exam on Tuesday May 19 at 2PM in Room 402. The members of his committee are: Tom Funkhouser, advisor, Szymon Rusinkiewicz, and Fei-Fei 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. -------------------------------- Abstract Automatic segmentation of 3D surface meshes into functional parts is a fundamental problem in computer graphics. While many algorithms have been developed over the last several years, there has been little work on the quantitative evaluation of how well they perform. In this project, we built a benchmark for quantitative evaluation of mesh segmentation algorithms. The benchmark comprises of 4,300 manual segmentations for 380 surface meshes of 19 different object categories. It also provides software for analyzing 11 geometric properties of segmentations and producing 4 quantitative metrics for comparison of segmentations. With the benchmark, we further investigate segmentation consistency within the same object category as well the planar reflection symmetry of segmentations. Our results suggest that people are remarkable consistent in the way that they segment most 3D surface meshes, that no one automatic segmentation algorithm is better than the others for all types of objects, and that algorithms based on non-local shape features seem to produce segmentations that most closely resemble ones made by humans. Reading List [Paper] [1] MARTIN, D., FOWLKES, C., TAL, D., AND MALIK, J. 2001. A database of human segmented natural images and its application to evaluating segmentation algorithms 936 and measuring ecological statistics. In in Proc. 8th Intl Conf. Computer Vision, 416�423. [2] UNNIKRISHNAN, R., PANTOFARU, C., AND HEBERT, M. 2005. A measure for objective evaluation of image segmentation algorithms. In Proceedings of the 2005 IEEE Conference on Computer Vision and Pattern Recognition (CVPR �05), Workshop on Empirical Evaluation Methods in Computer Vision, vol. 3, 34 �981 41. [3] HUANG, Q., AND DOM, B. 1995. Quantitative methods of evaluating image segmentation. In ICIP �95: Proceedings of the 1995 International Conference on Image Processing (Vol. 3)-Volume 3, IEEE Computer Society, Washington, DC, USA, 3053. [4] ATTENE, M., KATZ, S., MORTARA, M., PATANE, G., SPAGNUOLO, M., AND TAL, A. 2006. Mesh segmentation - a comparative study. In SMI �06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, IEEE Computer Society, Washington, DC, USA, 7. [5] GOLOVINSKIY, A., AND FUNKHOUSER, T. 2008. Randomized cuts for 3D mesh analysis. ACM Transactions on Graphics (Proc. SIGGRAPH ASIA) 27, 5 (Dec.). [6] KATZ, S., LEIFMAN, G., AND TAL, A. 2005. Mesh segmentation using feature point and core extraction. The Visual Computer 21, 8-10, 649�658. [7] ATTENE, M., FALCIDIENO, B., AND SPAGNUOLO, M. 2006. Hierarchical mesh segmentation based on fitting primitives. Vis. Comput. 22, 3, 181�193. [8] SHAPIRA, L., SHAMIR, A., AND COHEN-OR, D. 2008. Consistent mesh partitioning and skeletonisation using the shape diameter function. Vis. Comput. 24, 4, 249�259. [9] LAI, Y.-K., HU, S.-M., MARTIN, R. R., AND ROSIN, P. L. 2008. Fast mesh segmentation using random walks. In Symposium on Solid and Physical Modeling, 183�191. [10] HOFFMAN, D. D., AND SINGH, M. 1997. Salience of visual parts. Cognition 63, 29�78. [11] SHAMIR, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 28, 6, 1539�1556. [Textbook] Computer Graphics with OpenGL, Third Edition, Donald Hearn and M. Pauline Baker, Prentice Hall, 2004 ISBN: 0-13-015390-7.

1 0

CJ Bell general exam
by Melissa Lawson 14 May '09

14 May '09

CJ Bell will present his research seminar/general exam on Tuesday May 19 at 10AM in Room 402. The members of his committee are: David Walker, 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. ---------------------------------------------------------------------- ABSTRACT: We have developed a concurrent separation logic to reason about the correctness of programs that use produce and consume instructions for synchronized communication between threads. Our motivation behind such a logic is the decoupled software pipelining (DSWP) optimization in the context of proof-carrying code (PCC). PCC is a technique that allows untrusted code to be proven safe with respect to a desired security model. Such code, when accompanied by a formal proof of safety, can be validated and shown safe to execute. One advantage of PCC over its alternatives is that it ensures safe native code execution with minimal runtime checks. With an optimizing compiler, native code is typically faster. To generate proofs of safety, however, it is necessary that the optimizations preserve proof annotations. DSWP is an optimization that attempts to break while-loops into dependent tasks that run in parallel and communicate their dependencies through channels. The tasks are chosen to mitigate stalling of the entire operation when accessing resources that other tasks do not depend on. For example, a goal of DSWP is to use low-latency communication channels to reduce pipeline stalls caused by memory loads that, due to the variable latency of memory access, are difficult to prevent using optimizations such as instruction scheduling. Communication channels are a synchronization method that has not yet been explored in the context of concurrent separation logic, although other mechanisms such as locks and conditional critical regions have been investigated. Separation logic tracks resource ownership, which is particularly useful for DSWP in order to break loops into concurrent tasks. Our logic facilitates sound reasoning about the use of communication channels to pass values between threads. Furthermore, our logic reasons about the history of values produced and consumed. It may be used in any situation where the programmer desires to pass data between threads, but there is also potential for its use as a target language for a certifying implementation of the DSWP optimization in a PCC framework. ---------------------------------------------------------------------- TEXTBOOKS: Types and Programming Languages (Pierce, B.) Compiling with Proofs, ch. 1-6 (Necula, G.) ---------------------------------------------------------------------- PAPERS: [1] BI as an Assertion Language for Mutable Data Strunctures (Ishtiaq S., O'Hearn P.) [2] Resources, Concurrency, and Local Reasoning (O'Hearn P.) [3] Permission Accounting in Separation Logic (Bornat R.) [4] Types for Atomicity (Flanagan, Qadeer S.) [5] Analysis and Optimization of Explicitly Parallel Programs using the Parallel Program Graph Representation (Sarkar V.) [6] Automatic Thread Extraction with Decouples Software Pipelining (Ottoni G., August D.) [7] A Concurrent Execution Semantics for Parallel Program Graphs and Program Dependence Graphs (Sarkar V.) [8] Local Reasoning for Storable Locks and Threads (Gotsman A.) [9] A Verifiable SSA Program representation for Aggressive Compiler Optimization (Menon V. S.) [10] Revisiting the Sequential Programming Model for Multi-Core (Bridges M., August D.)

1 0

Talk Announcement -
by Ginny Hogan 13 May '09

13 May '09

TALK ANNOUNCEMENT Friday May 15, 1:30 PM TITLE: Discrete Methods for the Computational Analysis of Biological Networks and Pathways SPEAKER: Ron Y. Pinter, Dept. of Computer Science and the Rappaport School of Medicine, Technion - Israel Institute of Technology LOCATION: Carl Ichan Lab 280 ABSTRACT: Elucidating the structure and function of biological networks and pathways requires the development and the application of computational tools and techniques. Naturally, different methods are suitable for different kinds of analyses, e.g. employing discrete vs. continuous models, extracting qualitative vs. observing quantitative properties, and utilizing static vs. dynamic analyses. In this talk I will describe a number of discrete methods that we have devised recently to analyze both metabolic pathways as well as protein-protein interaction and regulation networks. In some cases these analyses have been static, allowing us to extract instructive information from the description of a network or a pathway; and in others - dynamic, aiming to understand and predict the behavior of a network or a pathway over time. In all cases I will present both the modeling as well as algorithmic issues along with the biological consequences that they have yielded. Specifically, the talk will include a detailed description of identifying composite network motifs, a method for the alignment of metabolic pathways and some of its applications, and the dynamic analysis of transient behavior in developmental pathways.

1 0

M Golightly general exam
by Melissa Lawson 12 May '09

12 May '09

Michael Golightly will present his research seminar/general exam on Friday May 15 at 10AM in Room 302 (note room). The members of his committee are: Vivek Pai, advisor, Larry Peterson, and Jen Rexford. 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: The PlanetLab global network testbed has grown to consist of over 1000 globally distributed nodes that run hundreds of research experiments concurrently, placing demands on its infrastructure that single- experiment testbeds do not face. While it is widely used in the networking community, very little research has examined the behavior of PlanetLab itself, particularly in the areas of workload and capacity analysis. In light of the number of papers and proposals devoted to resource allocation strategies, auction mechanisms, and testbed fairness, this lack of data is particularly surprising. In order to support continued successful growth of PlanetLab, and to help in planning future testbeds such as GENI, a detailed understanding of how the system is being used is essential. Toward this goal, our work presents a detailed analysis of both the current testbed state as well as some historical analysis using data provided by CoMon, a monitoring service for PlanetLab. We examine node- level behavior as well as experiment-centric behavior to understand how the system and its components are used in practice. We identify root causes of resource contention and workload imbalance, and offer solutions for abatement, finding that targeted investments in infrastructure have the potential to substantially alleviate contention. Through analyzing resource consumption, provision, and disparity, we identify the degree of altruism and selfishness among the users and sites that host PlanetLab nodes. Using this information, we explore the effectiveness of current policies that aim to provide fair sharing of resources. We then explore the appropriateness and feasibility of various resource allocation schemes using a data driven approach based on observed usage patterns. Reading List: [Text Book] [1] L. L. Peterson and B. S. Davie. Computer networks: a systems approach. Morgan Kaufmann, Amsterdam, 4th ed edition, 2007. [Papers] [2] N. Spring, L. Peterson, A. Bavier, and V. Pai. Using planetlab for network research: myths, realities, and best practices. SIGOPS Oper. Syst. Rev., 40(1):17-24, 2006. [3] B. Chun and A. Vahdat. Workload and failure characterization on a large-scale federated testbed. Technical Report IRB-TR-03-040, Intel Research Berkeley, Nov. 2003. [4] K. Park and V. S. Pai. Comon: a mostly-scalable monitoring system for planetlab. SIGOPS Oper. Syst. Rev., 40(1):65-74, 2006. [5] S. Bhatia, A. Kumar, M. Fiuczynski, and L. Peterson. Lightweight, high-resolution monitoring for troubleshooting production systems. In 8th USENIX Symposium on Operating System Design and Implementation (OSDI 2008), December 2008. [6] J. Shneidman, C. Ng, D. C. Parkes, A. AuYoung, A. C. Snoeren, A. Vahdat, and B. Chun. Why markets could (but don't currently) solve resource allocation problems in systems. In HOTOS'05: Proceedings of the 10th conference on Hot Topics in Operating Systems, pages 7-7, Berkeley, CA, USA, 2005. USENIX Association. [7] D. Oppenheimer, J. Albrecht, D. Patterson, and A. Vahdat. Design and implementation tradeoffs for wide-area resource discovery. In 14th IEEE International Symposium on High Performance Distributed Computing, 2005. HPDC-14. Proceedings, pages 113-124, 2005. [8] D. Oppenheimer, B. Chun, D. Patterson, A. C. Snoeren, and A. Vahdat. Service placement in a shared wide-area platform. In ATEC '06: Proceedings of the annual conference on USENIX '06 Annual Technical Conference, pages 26-26, Berkeley, CA, USA, 2006. USENIX Association. [9] Y. Fu, J. Chase, B. Chun, S. Schwab, and A. Vahdat. SHARP: An architecture for secure resource peering. In Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 133- 148. ACM New York, NY, USA, 2003. [10] R. Ricci, D. Oppenheimer, J. Lepreau, and A. Vahdat. Lessons from resource allocators for large-scale multiuser testbeds. SIGOPS Oper. Syst. Rev., 40(1):25-32, 2006.

1 0

A Vijayaraghavan general exam
by Melissa Lawson 12 May '09

12 May '09

Aravindan Vijayaraghavan will present his research seminar/general exam on Friday May 15 at 2PM in Room 302 (note room). The members of his committee are: Moses Charikar, advisor, Sanjeev Arora, 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 Many approximation algorithms proceed by finding a good partial solution and then recursing into a sub-instance to find the remaining solution. With this motivation, we study the problem of maximizing certain integer quadratic programs with a ratio objective. We first consider the Max-cut gain problem where the objective is to find a cut which maximizes the advantage over the random assignment, of the fraction of edges cut. Trevisan recently gave an algorithm, that uses just the eigenvector corresponding to the smallest eigenvalue (\lambda), which given a gain of G, obtains a cut with an exponentially small cut-gain ( exp(-1/ G)). He considers the 'gain ratio' (gain achieved by partial cuts i.e cuts (L,R) of a subset S of vertices) and obtains a exponential small gain-ratio (~ exp(-1/|\lambda|) ) and then progresses recursively. He further conjectures that a much better gain-ratio of \Omega(|\lambda|/log(|\lambda|)), which matches the SDP algorithm of Charikar-Wirth, is achievable. However, we refute this conjecture, by showing that the gain-ratio achieved by his algorithm is almost tight, thus showing that eigen-value based methods can only produce cuts with exponentially small gain (and gain-ratio). We then consider the ratio version of a general quadratic the program i.e maximize ratio of \sum_{ij} a_{ij}x_i x_j to the number of non-zero x_i values (where x_i can take values in {-1,0,1}). We strengthen the natural SDP relaxation with some additional constraints (similar to triangle inequalities) and give a rounding algorithm which obtains an approximation ratio of O(n^{1/3}). We also show an integrality gap of \Omega(n^{1/4}) for this stronger relaxation. (Based on joint work with Moses Charikar and Aditya Bhaskara) Reading list: Books/Surveys: 1. Approximation Algorithms by V.Vazirani - chapters 1-6, 12-21 2. Hoory, Linial, Wigderson. Expander graphs and their applications. (Chapters 2,3,4,7) 3. Arora, Barak. Complexity Theory: A Modern Approach. (PCP Chapters, 11,21,22) Research articles: 1. Luca Trevisan. Maxcut and the smallest eigenvalue. 2. Charikar, Wirth. Maximizing Quadratic programs:Extending the Groethendieck's inequality. 3. Alon, Naor. Approximating the Cut-Norm via Grothendieck's Inequality 4. Khot, O'Donnell. SDP gaps and UGC-hardness for Max-Cut-Gain 5. Khot, Kindler, Mossel, O'Donnell. Optimal inapproximability results for MAX-CUT and other two-variable CSPs? 6. Feige, Kortsartz, Peleg. The Dense k-subgraph problem. 7. Feige. Relations between average case complexity and approximation complexity 8. Feige, Selster. On the densest k-subgraph problem. 9. Alon, Krivelevich, Sudakov. Finding a large hidden clique in a random graph 10. Charikar, Makarychev, Makarychev. Near-optimal algorithms for unique games. 11. Charikar, Markarychev, Makarychev. Integrality Gaps for Sherali-Adams Relaxations. 12. Raecke. Optimal Hierarchical Decompositions for Congestion minimization in networks 13. Fakcharoenphol, Rao, Talwar. A tight bound on approximating arbitrary metrics by tree metrics 14. Arora, Khot, Kolla, Steurer, Tulsiani and Vishnoi. Unique Games on Expanding Constraint Graphs are Easy

1 0

Room Change - Huang generals tomorrow
by Melissa Lawson 11 May '09

11 May '09

Note room change for Jialu Huang's general exam tomorrow. Exam has been moved to Room 302; time remains same - 2PM --Melissa

1 0

FW: Max Welling, May 11, 12:30pm (lunch at 12pm)
by Ginny Hogan 11 May '09

11 May '09

Max Welling from UCI will give a talk on May 11 at 12:30 (lunch served at 12:00) in CS 302. He will also host a discussion group at 4:30pm. See end of this email for instructions on how to schedule a meeting with Max. Title: On Herding Dynamical Weights and Fractal Attractors Abstract: Learning the parameters of a Markov Random Field is intractable. To circumvent part of this intractability, I propose to give up on the idea of trying to obtain point estimates. Inspired by the concept of "dynamical synapses", a dynamical system is introduced that generates sequences of pseudo-samples that are guaranteed to satisfy the moment constraints of the associated maximum likelihood problem. This dynamical system is deterministic, yet non-periodic with Lyaponov exponents all equal to zero, and its attractor set has fractal properties. I will discuss how to leverage these ideas for classification and estimation and show experimental results for fully observed and restricted Boltzman machines. Title: On the Role of Smoothing in Topic Models (with Arthur Acuncion and Padhriac Smyth) Discussion Group @ 4:30PM, Location TBD Abstract: Latent Dirichlet analysis, or topic modeling, is a flexible latent variable framework for modeling high-dimensional, sparse count data. Various learning algorithms have been developed in recent years, including collapsed Gibbs sampling, variational inference, and maximum a posteriori estimation, and this variety motivates the need for careful empirical comparisons between these approaches. We first highlight the close connections between these approaches. We find that the main differences are attributable to the amount of smoothing applied to the counts. When the hyperparameters are optimized, the differences in performance among the algorithms diminish significantly. The ability of these algorithms to achieve similarly accurate solutions gives us the freedom to select computationally efficient approaches. On text corpora with thousands of documents, accurate topic models can be learned in several seconds, using the insights gained from this comparative study. If you'd like to meet Max on Monday, please: 1. Visit http://wass.princeton.edu. 2. Sign in using your OIT login. 3. Click on "Make an appointment." 4. Enter "mlvisit" where it says "Calendar owner's netid." 5. Reserve a spot on May 11 under "Meeting with Max Welling."

1 0

P Prabhu general exam - today
by Melissa Lawson 11 May '09

11 May '09

(short notice - scheduling conflict, exam will be today) Prakash Prabhu will present his research seminar/general exam **today, Monday May 11** at 1PM in Room 402. The members of his committee are: David August, advisor, David Walker, and JP Singh. 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. ----------------------------------------------------- Enabling Implicit Parallel Programming on Multi-Core Architectures With the advent of multi-core architectures in mainstream computing, the importance of thread-level parallelism in delivering application performance has become critical. Existing thread-centric programming paradigms like pthreads and OpenMP are explicit. Today, programmers explicitly specify parallelization techniques and manage access to data using locking constructs. Such explicitly written parallel programs, plagued by race conditions, deadlocks, and performance problems, are difficult to write, debug, and maintain. Even worse, they are also fragile and intimately tied to assumptions about the underlying parallel architecture. In contrast, automatic thread extraction is a promising alternative that does not suffer from these problems, but whose benefits are yet to be realized on real hardware for large programs. Recently, Bridges et al., proposed two extensions to a sequential programming language, showing substantial amounts of thread-level parallelism can be automatically extracted from sequential codes, while relying on state-of-the-art profiling and speculation techniques. These extensions are not explicitly parallel and change program semantics. Since these extensions may change a program's output, they cannot be automatically inferred. Following on the lines of Bridges et al., this work proposes a generalized set of implicitly parallel programming extensions to the C language, which enables a programmer to write correct code and reason sequentially. At the same time, it considerably enhances a compiler's ability to extract thread-level parallelism. This talk explains the semantics of these extensions and demonstrates their use in manual parallelization of several benchmark programs. [Text Books] [1] Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998 [2] Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2006. [Papers] [3] M. J. Bridges, N. Vachharajani, Y. Zhang, T. Jablin, and D. I. August. Revisiting the sequential programming model for multi-core. In Proceedings of the 40th Annual ACM/IEEE International Symposium on Microarchitecture (MICRO), December 2007. [4] Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni and David I. August. Speculative Decoupled Software Pipelining. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques (PACT), September 2007 [5] Christoph von Praun, Luis Ceze, Calin Caşcaval. Implicit parallelism with ordered transactions. In Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP), 2007 [6] Wen-mei Hwu et al., Implicitly Parallel Programming Models for Thousand-Core Microprocessors, In Proceedings of the 44th Design Automation Conference (DAC), 2007 [7] Robert Bocchino, Vikram Adve, Sarita Adve and Marc Snir. Parallel Programming Must Be Deterministic By Default. First USENIX Workshop on Hot Topics in Parallelism (HotPar), March 2009. [8] Monica S. Lam and Martin C. Rinard. Coarse-grain parallel programming in Jade. In Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP), pages: 94-105, 1991. [9] Eduard Ayguad´e et al., The Design of OpenMP Tasks, IEEE Transactions on Parallel and Distributed Systems (TPDS), March 2009 [10] David J. Pearce, Paul H.J. Kelly and Chris Hankin. Efficient field-sensitive pointer analysis of C. ACM Transactions on Programming Languages and Systems (TOPLAS), 2007 [11] R. Ghiya, L. J. Hendren and Y. Zhu. Detecting Parallelism in C Programs with Recursive Data Structures, Proceedings of the 7th International Conference on Compiler Construction (CC), page 159-173, 1998. [12] Chris Lattner, Andrew Lenharth, Vikram Adve. Making context-sensitive points-to analysis with heap cloning practical for the real world. In the Proceedings of the 2007 Programming Languages Design and Implementation conference, 2007. [13] Justiani and Laurie J. Hendren. Supporting Array Dependence Testing for an Optimizing/Parallelizing C Compiler. In the Proceedings of the 5th International Conference on Compiler Construction (CC), pages 309-323, 1994. [14] A. Tineo, F. Corbera, A. Navarro, R. Asenjo, and E.L. Zapata. A Novel Approach for Detecting Heap-based Loop-carried Dependences, Proceedings of the International Conference on Parallel Processing(ICPP), 2005

1 0

A Bhaskara general exam
by Melissa Lawson 07 May '09

07 May '09

Aditya Bhaskara will present his research seminar/general exam on Thursday May 14 at 10AM in Room 302 (note room). The members of his committee are: Moses Charikar, advisor, Sanjeev Arora, and Bob Tarjan. 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 -------- We will look at the densest-k-subgraph (DkS) problem: Given a graph G(V,E) and a parameter k, find a set of k vertices such that the number of edges among them is maximized. The problem is quite well-studied, but there is a big gap between the known algorithms and inapproximability results. There are combinatorial (greedy, path-based), and SDP based approaches known for the problem, which do well in different ranges of the parameters (degree, k). A common barrier for these approaches is the case of random graphs G(n,p) with planted dense subgraphs of size $k$. We thus propose and study a "Dense-vs-Random" problem: Distinguish a random graph of degree \Delta from the class of graphs with a k-subgraph of density (average degree) d. The question is to find the smallest $d$ for which this is possible (in terms of n, \Delta). For random graphs of degree n^{q} (0 < q < 1), we design algorithms that distinguish them from graphs with k-subgraphs of average degree >> k^q. The idea is to do an appropriate "local" counting. Interestingly, for such local counting, k^q seems to be a barrier, while a simple SDP based approach does better when q < 1/2. The main contribution is to use these "local structures" in obtaining algorithms for dense k-subgraph. We show how to do this for structures of certain special kinds. It seems reasonable to conjecture that this can be done with all structures. Doing this would imply an n^{1/4} approximation algorithm for dense k-subgraph. Our current techniques allow us to obtain a slightly worse ratio of n^{3/11}. It is an interesting question to go beyond n^{1/4} -- this is the limit for both the SDP and the local counting approaches. (Joint work with Moses Charikar and Aravindan Vijayaraghavan) Reading list ------- ---- N. Alon, M. Krivelevich and B. Sudakov, Finding a large hidden clique in a random graph, Random Structures and Algorithms 13 (1998), 457-466. Frank McSherry, Spectral Partitioning of Random Graphs. Proceedings of FOCS 2001, 529-537. Moses Charikar and Anthony Wirth, Maximizing Quadratic Programs: Extending Grothendieck's Inequality. Noga Alon and Assaf Naor, Approximating the cut-norm via Grothendieck's inequality. Luca Trevisan, Max Cut and the Smallest Eigenvalue. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani and Nisheeth K. Vishnoi, Unique games on expanding constraint graphs are easy. Moses Charikar, Konstantin Makarychev and Yury Makarychev, Near-Optimal Algorithms for Unique Games. Uriel Feige, Relations between Average Case Complexity and Approximation Complexity. U. Feige and M. Seltser, On the densest $k$-subgraph problems. Moses Charikar, Konstantin Makarychev and Yury Makarychev, Integrality Gaps for Sherali-Adams Relaxations. Uri Feige and Robert Krauthgamer, The probable value of the Lovasz-Schrijver relaxations for maximum independent set. Tom Leighton and Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Sanjeev Arora, Satish Rao and Umesh Vazirani, Expander Flows, Geometric Embeddings, and Graph Partitionings. Books ----- Vijay Vazirani, Approximation Algorithms (Chapters 1-6, 12, 16, 19-22). Shlomo Hoory, Nati Linial, Avi Wigderson, Expander Graphs and their Applications (Chapters 1-4, 7). Sanjeev Arora, Boaz Barak, Computational Complexity: A modern approach (Chapters 1-11, 13, 21-22).

1 0

C Park general exam
by Melissa Lawson 07 May '09

07 May '09

Chris Park will present his research seminar/general exam on Wednesday May 13 at 10AM in Room 402. The members of his committee are: Olga Troyanskaya, advisor, Rob Schapire, and David Blei. 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 Inferring heterogeneous biological networks from heterogeneous data. With the advancement of quantitative biology, there has been a dramatic increase in functional genomic data. Using these heterogeneous genomic data which includes protein-protein interaction, gene expression, localization, and gene knockout studies has enabled researchers to construct functional gene networks. In functional gene networks, each edge represents the probabilistic support for a functional relationship between two genes. However in practice, the goal of biology is to understand further depth of the relationship between genes, beyond the abstract notion of a functional relation. In this work, we expand the depth and breadth of functional gene networks. We use prior biological knowledge of gene interactions types to construct an interaction ontology, which enables us to predict interaction types between genes using a Bayesian hierarchical framework. Ultimately, our work provides further insight into the genetic wiring of the cell. ---------------------------------------- Reading list Book: [1] Pattern Recognition and Machine Learning. by C. M. Bishop. Chapter 1~4, 6~9, 12~14 Papers: 1. Hierarchical multi-label prediction of gene function. Barutcuoglu, Z.; Schapire, R.E.; Troyanskaya, O.G. , Bioinformatics, (2006) 2. Discovery of biological networks from diverse functional genomic data. Myers, C.L.; Robson, D.; Wible, A.; Hibbs, M.A.; Chiriac, C.; Theesfeld, C.L.; Dolinski, K.; Troyanskaya, O.G. , Genome Biology, (2005) 3. Using Bayesian networks to analyze expression data. Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe'er. In RECOMB 4, pages 127-135. ACM Press, 2000. 4. Causal protein-signaling networks derived from multiparameter single-cell data. Sachs, K., Perez, O., Pe'er, D., Lauffenburger, D. A. & Nolan, G. P. Science 308, 523-529 (2005). 5. Conserved patterns of protein interaction in multiple species. Sharan, R., Suthram, S., Kelley, R. M., Kuhn, T., McCuine, S., Uetz, P., Sittler, T., Karp, R. M., and Ideker, T. /Proc Natl Acad Sci U S A. / *8*:102(6) 1974-79 (2005) 6. Genomic analysis of regulatory network dynamics reveals large topological changes. Luscombe, N., & et al. (2004). Nature, 431, 308. 7. Statistical significance for genome-wide studies. Storey JD and Tibshirani R. Proceedings of the National Academy of Sciences, 100: 9440-9445 (2003). 8. Cluster analysis and display of genome-wide expression patterns. Michael B. Eisen, Paul T. Spellman, Patrick O. Brown, and David Botstein PNAS, Dec (1998); 95: 14863 - 14868. 9. Genetics of global gene expression. Rockman, Kruglyak (2006). Nature Review Genetics 7:862-72. 10. An improved map of conserved regulatory sites for Saccharomyces cerevisiae. MacIsaac KD, Wang T, Gordon DB, Gifford DK, Stormo GD, Fraenkel E. BMC Bioinformatics. 2006 Mar 7;7:113.

1 0