- talks - lists.cs.princeton.edu

C Kim FPO
by Melissa Lawson 04 Jun '09

04 Jun '09

Chang Kim will present his FPO on Tuesday June 9 at 10 AM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Mike Freedman and Albert Greenberg (AT&T), readers; Vivek Pai and Margaret Martonosi, nonreaders. A copy of his thesis, "Scalable and Efficient Self-Configuring Networks", is on display in Room 310. Everyone is invited to attend his talk.

1 0

(no subject)
by Ginny Hogan 03 Jun '09

03 Jun '09

When: Wednesday, June 10, 2009 3:30 PM (EDT) Where: AT&T Shannon Laboratory Florham Park NJ auditorium, C050 Simulcast to Middletown, MT A3_4G23 Also available via NetMeeting. Details to follow. Reception: 4:30pm-5:30pm in the Florham Park Cafeteria *~*~*~*~*~*~*~*~*~* Frontiers in Research and Education in Computing: A View from the National Science Foundation Jeannette M. Wing President's Professor of Computer Science, Computer Science Department, Carnegie Mellon University Assistant Director, Computer and Information Science and Engineering Directorate, National Science Foundation Abstract: The NSF Computer and Information Science and Engineering Directorate funds 84% of all academic computer science research in the United States. I will present highlights of CISE's research and education programs, including current interests in cyber-enabled discovery and innovation, cyber physical systems, data-intensive computing, network science and engineering, socially intelligent computing, and trustworthy computing; and future interests in information technology's role in energy and the environment and the intersection of computer science and economics. I will also put NSF's investments in computing within the broader national and international context. Bio: Dr. Jeannette M. Wing is the President's Professor of Computer Science in the Computer Science Department at Carnegie Mellon University. She received her S.B. and S.M. degrees in Electrical Engineering and Computer Science in 1979 and her Ph.D. degree in Computer Science in 1983, all from the Massachusetts Institute of Technology. From 2004-2007, she was Head of the Computer Science Department at Carnegie Mellon. Currently on leave from CMU, she is the Assistant Director of the Computer and Information Science and Engineering Directorate at the National Science Foundation. Professor Wing's general research interests are in the areas of specification and verification, concurrent and distributed systems, programming languages, and software engineering. Her current focus is on the foundations of trustworthy computing. Professor Wing was or is on the editorial board of eleven journals. She has been a member of many advisory boards, including: the Networking and Information Technology (NITRD) Technical Advisory Group to the President's Council of Advisors on Science and Tecbnology (PCAST), the National Academies of Sciences's Computer Science and Telecommunications Board, ACM Council, the DARPA Information Science and Technology (ISAT) Board, NSF's CISE Advisory Committee, Microsoft's Trustworthy Computing Academic Advisory Board, and the Intel Research Pittsburgh's Advisory Board. She is a member of the Sloan Research Fellowships Program Committee. She is a member of AAAS, ACM, IEEE, Sigma Xi, Phi Beta Kappa, Tau Beta Pi, and Eta Kappa Nu. Professor Wing is an AAAS Fellow, ACM Fellow, and IEEE Fellow.

1 0

Talk Today - Friday May 15th 1:30 pm Carl Ican Lab 280
by Ginny Hogan 15 May '09

15 May '09

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

S Sen general exam
by Melissa Lawson 14 May '09

14 May '09

Sid Sen will present his research seminar/general exam on Wednesday May 20 at 1:30PM in Room 402. The members of his committee are: Mike Freedman and Bob Tarjan, co-advisors, 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 -------- We work at the boundary of systems and theory with the goal of designing data structures and algorithms for scalable, fault-tolerant distributed systems and other applications. This talk presents foundational progress on both sides, guided by a common theme: simplicity. That is, we allow complexity in the analysis of our designs, not their implementations. On the theory side, we present two new data structures for organizing information: the rank-pairing heap and the rank-balanced tree. Rank-pairing heaps use the minimum balance information possible in arguably the simplest way, matching the performance guarantees of Fibonacci heaps with no cascading structural changes. Rank-balanced trees support insertion and deletion in O(1) amortized time and at most two rotations worst-case, improving on red-black trees. A novel analysis based on an exponential potential function shows that nodes in a rank-balanced tree are rebalanced exponentially infrequently in their heights. We are conducting a thorough experimental evaluation of these data structures, with promising preliminary results. On the systems side, we propose a simple architecture for making fault tolerant protocols scalable and efficient in the wide area. We present Prophecy, a system that interposes itself between clients and a service replica group to minimize request replication when results are historically consistent. Prophecy uses compact sketching and load-balancing to provide what we call delay-once consistency: informally, faulty nodes can return only stale (not arbitrary) data and only for an exponentially-small number of times. We have implemented Prophecy and demonstrated its high throughput and scalability compared to Byzantine fault-tolerant (BFT) and quorum-based systems. We also present a measurement study of popular websites that demonstrates a high extent of static (historically- consistent) data. Reading list ------------ Books: 1. Thomas. H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, Cambridge, MA, 2nd edition, 2001. [Chapters 1-26, 34-35] 2. Andrew S. Tanenbaum and Maarten van Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, Upper Saddle River, NJ, 2002. [Chapters 7-8] Papers: [1] R. E. Tarjan. Amortized computational complexity. SIAM J. Alg. Disc. Meth., 6:306-318, 1985. [2] Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. [3] Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, 1985. [4] M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1(1):111-129, 1986. [5] Robert E. Tarjan. Efficiency of a good but not linear set union algorithm. J. of the ACM, 22(2):215-225, 1975. [6] Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. [7] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, 1982. [8] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In OSDI, pages 173-186, 1999. [9] Ramakrishna Kotla, Lorenzo Alvisi, Michael Dahlin, Allen Clement, and Edmund L. Wong. Zyzzyva: speculative byzantine fault tolerance. In SOSP, pages 45-58, 2007. [10] Yanhua Mao, Flavio Paiva Junqueira, and Keith Marzullo. Mencius: Building efficient replicated state machine for WANs. In OSDI, pages 369-384, 2008. [11] Brian F. Cooper, Raghu Ramakrishnan, Utkarsh Srivastava, Adam Silberstein, Philip Bohannon, Hans-Arno Jacobsen, Nick Puz, Daniel Weaver, and Ramana Yerneni. PNUTS: Yahoo!'s hosted data serving platform. VLDB, 1(2):1277-1288, 2008. [12] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon's highly available key-value store. In SOSP, pages 205-220, 2007.

1 0

A Pop general exam
by Melissa Lawson 14 May '09

14 May '09

Ana Pop will present her research seminar/general exam on Wednesday May 20 at 10AM in room 402. The members of her committee are: Olga Troyanskaya, advisor, David Blei, and Rob Schapire. 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: ------ The availability of genome-scale data has enabled gene function prediction for different organisms. Computational approaches to this problem have aimed to integrate all this heterogeneous information. One method that has been applied with great success has been Bayesian data integration, which, given the genomic data and known functional relationships, can predict other functional relationships and organize the genomic information into functional relationship networks. In addition to understanding the function of genes we also aim to understand the progression of these genes' functions and interactions as the organism develops. Computational approaches have been applied mostly to simple organisms such as the very well-studied Saccharomyces cerevisiae (baker's yeast). More complex organisms, such as Arabidopsis thaliana (the model organism for plants), which is the focus of this project, are much more challenging to analyze as they are substantially more complex and have different tissues types and development stages. Therefore, this plant is ideal for a developmental gene functional networks study. We have created a global functional network for Arabidopsis where nodes are genes and links between the nodes represent a functional relationship (the link weight represents the probability of interaction). Analysis of this network showed that the top few hundred highest scoring functional relationships are between genes related to photosynthesis. In addition to the global network, we also have biological process context-specific networks for Arabidopsis, which shows gene functional relationships in different biological process contexts (such as cell cycle or DNA replication). We are also extending this model to determine developmental progression of gene function both globally and in various development-stage contexts. We expect that overlaying the biological process context-specific networks with the development stage context-specific networks will shed light on the way gene function progresses over the different developmental stages of the plant. ------ Reading List: ------ [Book] Artificial Intelligence: A Modern Approach (Second Edition) by Stuart Russell and Peter Norvig - section V (Uncertain knowledge and reasoning) - section VI (Learning) [1] C Huttenhower, O Troyanskaya; Bayesian data integration: a functional perspective; Comput. Syst. Bioinformatics, 2006 [2] Guan Y, Myers CL, Hess DC, Barutcuoglu Z, Caudy AA, Troyanskaya OG: Predicting gene function in a hierarchical context with an ensemble of classifiers. Genome Biol 2008, 9(suppl 1):S3. [3] Curtis Huttenhower, Erin M. Haley, Matthew A. Hibbs, Vanessa Dumeaux, Daniel R. Barrett, Hilary A. Coller, and Olga G. Troyanskaya. Exploring the human genome with functional maps, Genome Research 2009 [4] S Rogers, M Girolami, A Bayesian regression approach to the inference of regulatory networks from gene expression data., Bioinformatics, Vol. 21, No. 14. (15 July 2005), pp. 3131-3137 [5] Paul Pavlidis, Jason Weston, Jinsong Cai and William Noble Grundy, Learning gene functional classifications from multiple data types, Journal of Computational Biology. 9(2):401-411, 2002 [6] Quackenbush J., Computational analysis of microarray data., Nat Rev Genet. 2001 Jun;2(6):418-27 [7] Brendan J. Frey and Delbert Dueck, Clustering by Passing Messages Between Data Points, (11 January 2007) Science [8] Alter O, Brown PO, Botstein D (2000) Singular value decomposition for genomewide expression data processing and modeling. Proc Natl Acad Sci USA 97:10101-10106. [9] Boyes et al., 2001 D.C. Boyes, A.M. Zayed, R. Ascenzi, A.J. McCaskill, N.E. Hoffman and K.R. Davis, Growth stage-based phenotypic analysis of Arabidopsis: a model for high throughput functional genomics in plants, Plant Cell 13 (2001), pp. 1499-1510. [10] S.M. Brady et. al. A high-resolution root spatiotemporal map reveals dominant expression patterns. Science 318 (2007), 801-806 [11] Anjali Iyer-Pascuzzi, June Simpson, Luis Herrera-Estrella, Philip N Benfey, Functional genomics of Arabidopsis root functional genomics, Current Opinion in Plant Biology, In Press, Corrected Proof, Available online 29 December 2008

1 0

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