May 2009 - talks - lists.cs.princeton.edu

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

M Meola general exam
by Melissa Lawson 07 May '09

07 May '09

Matt Meola will present his research seminar/general exam on Wednesday May 13 at 2PM in Room 402. The members of his committee are: David Walker, advisor, Andrew Appel, and Ed Felten. 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 -------- As semiconductor manufacturing technologies improve, feature sizes get smaller, and transistors more densely packed, computer users face an ever-increasing chance that cosmic rays and other sources of high energy particles will disrupt the workings of their processors. When implementing cryptographic algorithms, security protocols, long-running simulations, and safety-critical systems, software developers must consider the possibility that such intermittent hardware faults will cause irreparable harm to their applications. Boneh, DeMillo, and Lipton were the first to show that a single fault could be exploited to break common implementations of RSA. Others followed, demonstrating exploits of cryptosystems and runtime systems achieved by inducing transient faults. To support the higher degrees of confidence required in these critical applications, we have developed a new logic for reasoning about faulty programs. Our logic allows the verification of programs even in the presence of transient faults. It operates over a standard language of imperative while programs augmented with a single new instruction to indicate the possibility of faults at particular program points. The logic itself is a relative of Separation Logic in which the separating conjunction is used to reason about the limits to which faults may affect different parts of program state. As much as is practical, the logic is intended to be agnostic of the particular model used to decide when faults may occur. In particular, our current work deals with standard fault models that allow a certain maximum number of faults to occur in program variables in a single run of the program and limits faults according to how they affect data (typically either allowing only a single bit flip or allowing arbitrary changes in value). Faults in control-flow and many control logic faults (such as misinterpretation of opcodes) are ignored, except where they can be simulated by data faults. We prove the logic is sound and illustrate how to use it on several simple examples, including a simplified, idealized version of the RSA message signing algorithm. We show how the introduction of a modal connective helps to simplify program assertions and facilitate the reasoning process. Books ----- Pierce, B.C. Types and Programming Languages. MIT Press, 2002. Ch 1, 2, 4, 5 of Huth, M.R.A. and Ryan, M.D. Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, 2000. Papers ------ [1] Bar-El, H., Choukri, H., Naccache, D., Tunstall, M., and Whelan, C. The Sorcerers Apprentice Guide to Fault Attacks. Proc. IEEE, Vol. 94. 370-382, Feb. 2006. [2] Barthe, G., Grégoire, B., and Zanella Béguelin, S. 2009. Formal certification of code-based cryptographic proofs. In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Savannah, GA, USA, January 21 - 23, 2009). POPL '09. ACM, New York, NY, 90-101. [3] Boneh, D., DeMillo, R., and Lipton, R., On the importance of checking cryptographic protocols for faults, Journal of Cryptology 14 (2001). 101-119. [4] Chang, J., G. A. Reis and D. I. August. Non-Uniform Fault Tolerance. In Proceedings of the 2nd Workshop on Architectural Reliability (WAR), December 2006. [5] Ishtiaq, S. and O'Hearn, P. Bi as an assertion language for mutable data structures. In Proceedings of the 28th ACM Symposium on Principles of Programming Languages, London, United Kingdom, 2001, 14-26. [6] Perry, F., Mackey, L., Reis, G. A., Ligatti, J., August, D. I., and Walker, D. 2007. Fault-tolerant typed assembly language. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, California, USA, June 10 - 13, 2007). PLDI '07. ACM, New York, NY, 42-53. [7] Rebaudengo, M., Sonza Reorda, M., Torchiano, M., and Violante, M., Soft-error Detection through Software Fault-Tolerance techniques, in: IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, 1999, 210-218. [8] Reis, G. A., Chang, J., and August, D. I. 2007. Automatic Instruction-Level Software-Only Recovery. IEEE Micro 27, 1 (Jan. 2007), 36-47. [9] Shirvani, P. P., Saxena, N., and McCluskey, E. J. 2000. Software-implemented EDAC protection against SEUs. In IEEE Transactions on Reliability. Vol. 49. 273284. [10] Walker, D., Mackey, L., Ligatti, J., Reis, G. A., and August, D. I. 2006. Static typing for a faulty lambda calculus. In Proceedings of the Eleventh ACM SIGPLAN international Conference on Functional Programming (Portland, Oregon, USA, September 16 - 21, 2006). ICFP '06. ACM, New York, NY, 38-49.

1 0

J Huang general exam
by Melissa Lawson 05 May '09

05 May '09

Jialu Huang will present her research seminar/general exam on Tuesday May 12 at 2PM in room 402. The members of her committee are: David August, advisor, Brian Kernighan, and Andrew Appel. 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. ============================================ General abstract: While multi-core systems have become prevalent, using them efficiently remains an unsolved problem. DOALL is a highly efficient parallelization technique, however, cross-iteration dependences limit DOALL's applicability. Decoupled software pipelining (DSWP) partitions the code into stages with dependences flowing unidirectionally from earlier stages to later stages. DSWP is more generally applicable than DOALL, but its scalability is limited by the number of stages and by the workload in each stage. Parallel stage decoupled software pipelining (PS-DSWP) addresses this problem by enabling DOALL parallelization to some stages of a DSWP pipeline in loops where DOALL wasn't originally applicable. Inspired by the idea that DSWP can make DOALL more applicable, this work proposes other parallelization techniques can become more broadly applicable through the use of DSWP. LOCALWRITE, which requires each thread to only update the data belonging only to itself, if applied alone, suffers from redundant computations. Introducing LOCALWRITE into a DSWP framework, removes this limitation, by having a separate DOALL stage produce the iteration state to the LOCALWRITE stages. Experiments show combining all three parallelizations (DOALL, LOCALWRITE, DSWP) yields performance superior to applying any of these techniques alone. Reading List: Books: [1] Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998. Chapter 1~13, 17~21. [2] Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2001. Chapter 9, 10. Papers: [1] Raman, E., Ottoni, G., Raman, A., Bridges, M. J., and August, D. I. 2008. Parallel-stage decoupled software pipelining. In Proceedings of the Sixth Annual IEEE/ACM international Symposium on Code Generation and Optimization (Boston, MA, USA, April 05 - 09, 2008). CGO '08. ACM, New York, NY, 114-123. DOI= http://doi.acm.org/10.1145/1356058.1356074 [2] Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August. Automatic Thread Extraction with Decoupled Software Pipelining. In Proceedings of the 38th IEEE/ACM International Symposium on Microarchitecture (MICRO), November 2005. [3] Matthew J. Bridges, Neil Vachharajani, Yun Zhang, Thomas Jablin, David I. August, "Revisiting the Sequential Programming Model for the Multicore Era," IEEE Micro, vol. 28, no. 1, pp. 12-20, Jan./Feb. 2008, doi:10.1109/MM.2008.13. [4] Vachharajani, N., Rangan, R., Raman, E., Bridges, M. J., Ottoni, G., and August, D. I. 2007. Speculative Decoupled Software Pipelining. In Proceedings of the 16th international Conference on Parallel Architecture and Compilation Techniques (September 15 - 19, 2007). PACT. IEEE Computer Society, Washington, DC, 49-59. DOI= http://dx.doi.org/10.1109/PACT.2007.66. [5] Singh, D. E., Martin, M. J., and Rivera, F. F. 2005. Runtime characterisation of irregular accesses applied to parallelisation of irregular reductions. Int. J. Comput. Sci. Eng. 1, 1 (Feb. 2005), 1-14. DOI= http://dx.doi.org/10.1504/IJCSE.2005.008906. [6] Gutiérrez, E., Plata, O. G., and Zapata, E. L. 1999. On Automatic Parallelization of Irregular Reductions on Scalable Shared Memory Systems. In Proceedings of the 5th international Euro-Par Conference on Parallel Processing (August 31 - September 03, 1999). P. Amestoy, P. Berger, M. J. Daydé, I. S. Duff, V. Frayssé, L. Giraud, and D. Ruiz, Eds. Lecture Notes In Computer Science, vol. 1685. Springer-Verlag, London, 422-429. [7] Eladio Gutiérrez, Oscar Plata, Emilio L. Zapata, "Improving Parallel Irregular Reductions Using Partial Array Expansion," sc,pp.56, ACM/IEEE SC 2001 Conference (SC 2001), 2001. [8] Saltz, J. H., Mirchandaney, R., and Crowley, K. 1989. The doconsider loop. In Proceedings of the 3rd international Conference on Supercomputing (Crete, Greece, June 05 - 09, 1989). ICS '89. ACM, New York, NY, 29-40. DOI= http://doi.acm.org/10.1145/318789.318794. [9] Y. Lin and D. Padua. On the Automatic Parallelization of Sparse and Irregular Fortran Programs. Scientific Programming, 7(1999), pp. 231-246. ISSN 1058-9244, IOS Press. [10] Y. Lin and D. Padua. Analysis of Irregular Single-indexed Arrays and Its Applications in Compiler Optimizations. In Proceedings of the 9th International Conference on Compiler Construction. Berlin, Germany, March 2000.

1 0

J Hung general exam
by Melissa Lawson 05 May '09

05 May '09

Jack Tzu-Han Hung will present his research seminar/general exam on Tuesday May 12 at 10AM in Room 402. the members of his committee are: David August, advisor, Margaret Martonosi, and Doug Clark. 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: Recently, the multicore systems have emerged as the dominate and promising architecture in the computing area. Unfortunately, a parallelizing compiler is essential to extract the potential parallelism from the existing sequential programs and utilize the power of multicore systems. Independent multi-threading (e.g., DOALL) and pipelined multi-threading (e.g., decouple software pipelining, DSWP) parallelization techniques have been researched extensively. However, each has its own advantages and limitations. On one hand, DOALL exploits data parallelism and scales well to the number of cores; however, it requires the lack of loop-carried dependencies and thus suffers from its applicability. On the other hand, DSWP handles the program dependencies via the use of communication queue and makes it applicable to more programs; however, the scalability of this approach is limited by the number of stages in the pipeline, which is usually far less than the number of cores. In this work, we propose two techniques to enhance the scalability of DSWP. First, instead of being inner-loop-blind, as DSWP does, we examine the structure of inner loops in the pipeline and exploit the DOALL opportunities if applicable. This improves the scalability of DSWP since the additional cores could be used for executing DOALL inner loops. Second, we optimize the communication for loop live-in and live-out variables by performing pre- and post-partitioning analyses. The post-partitioning analysis leverages the existing liveness analysis and is applied for each partition, instead of the entire loop. The pre-partitioning analysis takes the communication cost into consideration and could achieve better partitioning. Our initial results show a speedup up to 5.4x for 052.alvinn and ECLAT. Reading List: [Text Books] * Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998. * Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2006. [Papers] * Thies, W., Chandrasekhar, V., and Amarasinghe, S. 2007. A Practical Approach to Exploiting Coarse-Grained Pipeline Parallelism in C Programs. In Proceedings of the 40th Annual IEEE/ACM international Symposium on Microarchitecture (December 01 - 05, 2007). * Gordon, M. I., Thies, W., and Amarasinghe, S. 2006. Exploiting coarse-grained task, data, and pipeline parallelism in stream programs. In Proceedings of the 12th international Conference on Architectural Support For Programming Languages and Operating Systems (San Jose, California, USA, October 21 - 25, 2006). * Hongtao Zhong, Mojtaba Mehrara, Steve Lieberman, Scott Mahlke. " Uncovering Hidden Loop Level Parallelism in Sequential Applications". The 14th International Symposium on High-Performance Computer Architecture (HPCA), February, 2008. * Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August. Automatic Thread Extraction with Decoupled Software Pipelining. In Proceedings of the 38th IEEE/ACM International Symposium on Microarchitecture (MICRO), November 2005. * EaswaranRaman, Guilherme Ottoni, Arun Raman, Matthew Bridges, and David I. August. Parallel-Stage Decoupled Software Pipelining. In Proceedings of the 2008 International Symposium on Code Generation and Optimization (CGO), April 2008. * 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. * Guilherme Ottoni and David I. August. Global Multi-Threaded Instruction Scheduling: Technique and Initial Results. In Proceedings of the Sixth Workshop on Explicitly Parallel Instruction Computer Architectures and Compiler Technology (EPIC), March 2007. * J. R. B. Davies. Parallel loop constructs for multiprocessors. Master's thesis, Department of Computer Science, University of Illinois, Urbana, IL, May 1981. * J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9:319-349, July 1987.

1 0

M Hardt general exam
by Melissa Lawson 05 May '09

05 May '09

Moritz Hardt will present his research seminar/general exam on Monday May 11 at 2PM in Room 302 (note room). The members of his committee are: Boaz Barak, advisor, Sanjeev Arora, 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. -------------------------------------------------- I. Title + abstract What are plausible hard instances for Unique Games? Unique Games are a family of constraint satisfaction problems conjectured to be NP-hard. This conjecture due to Khot implies that simple semidefinite programs (SDP) achieve optimal approximation ratios for several important problems including Max-Cut and Vertex Cover. Unfortunately, little evidence in support of the conjecture exists. Indeed, random instances of Unique Games are known to be easy. In this work we thus address the question: What are plausible hard instances for Unique Games? Our approach is to consider the refutation problem induced by subsampling a given SDP gap instance to constant degree. While subsampling preserves global parameters such as the integrality gap, the lack of local structure may lead to computational hardness. In support of our methodology, we observe that a constant degree subsample of essentially any unsatisfiable k-CSP instance gives rise to strong lower bounds in the Lasserre SDP hierarchy so long as k is greater than 3. Based on the work of Charikar, Makarychev and Makarychev, we also show that for 2-CSPs and Unique Games a constant degree subsample of any unsatisfiable instance gives strong lower bounds in the Sherali-Adams linear programming hierarchy. Unfortunately, our approach can only go so far. Appealing to Grothendieck's inequality, we show that for any 2-CSP the induced refutation problem is solvable in polynomial time. We then consider the question whether known SDP gaps withstand additional constraints when subsampled to constant degree. Somewhat surprisingly, we can show that already the triangle inequalities annihilate the integrality gap of the well known Feige-Schechtman gap instance for Max-Cut. This remains true even in a constant degree subsample. As for a future research direction, similar ideas could apply to all known Unique Games gap instances. My talk is based on ongoing research with Boaz Barak, Thomas Holenstein and David Steurer. II. Reading list Books: * Arora, Barak. Computational Complexity. Chapters 11,13,14,18--23 Papers: [Ale03] Alekhnovich. More on average case vs approximation complexity [ABW09] Applebaum, Barak, Wigderson. Public Key Cryptography from Different Assumptions [AKK+08] Arora, Khot, Kolla, Steurer, Tulsiani and Vishnoi. Unique Games on Expanding Constraint Graphs are Easy [CMM09] Charikar, Makarychev, Makarychev. Integrality Gaps for Sherali- Adams Relaxations [Fei02] Feige. Relations between Average Case Complexity and Approximation Complexity [FS02] Feige and Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT [Hol07] Holenstein. Parallel Repetition: Simplifications and the no-signaling case [KKMO04] Khot, Kindler, Mossel, O'Donnell. Optimal inapproximability results for max-cut and other 2-variable CSPs? [KV05] Khot, Vishnoi. The unique games conjecture, integrality gap for cut problems, and embeddability of negative type metrics into l1. [Rag08] Raghavendra. Optimal Algorithms and Inapproximability Results for Every CSP? [Sch08] Schoenebeck. Linear Level Lasserre Lower Bounds for Certain k-CSPs [TTV09] Trevisan, Tulsiani, Vadhan. Regularity, Boosting, and Efficiently

1 0

T Yue general exam
by Melissa Lawson 05 May '09

05 May '09

Tao Yue will present his research seminar/general exam on Monday May 11 at 10AM in room 402. The members of his committee are: Mona Singh, advisor, Olga Troyanskaya, and Tom Funkhouser. 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 --------- Sequence similarity has long been used to find orthologs between proteins in different species, or to find paralogs within a species. Predictions of these evolutionary relationships can be exploited to infer and transfer functional annotations between proteins. In the past decade, high-throughput screening techniques have enabled the construction of protein interaction networks for many model organisms. In addition to direct protein interactions, other associations can also be made between pairs of proteins: coexpression, phylogenetic, neighborhood, gene fusion, etc. Such networks provide the opportunity to characterize a protein not just by its sequence, but by its interaction and association partners. This talk explains how to exploit these networks to detect functionally similar proteins between different species. Such networks, particularly the protein interaction networks, provide more direct evidence of function than does sequence similarity. We evaluate the power of various metrics for uncovering functionally similar proteins without using sequence similarity. In addition, we apply Rankprop, a diffusion-based process that has previously been used on sequence similarity, to these networks. We show that the use of networks from multiple organisms yields improvements in precision and recall. Furthermore, this procedure can be used to disambiguate predictions made by sequence-based methods, as well as correct errors. These techniques show promising applications as more interaction data becomes available. They also have potential future applications to the detection of analogous proteins, i.e., those that evolved the same function independently and thus lack sequence similarity. TEXTBOOK --------- Mount, Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press, 2004. Chapters 1-7, 11. PAPERS: General area: Protein networks --------------------------------------- Barabasi and Oltvai, Network Biology: Understanding the Cell's Functional Organization. Nature Reviews Genetics, February 2004, 101-113. Nabieva and Singh, Protein function prediction via analysis of interactomes. Prediction of Protein Structures, Functions, and Interactions (ed J. Bujnicki), 2009. Zhu et al, Getting connected: analysis and principles of biological networks. Genes & Developmnent 21 (2007): 1010-1024. PAPERS: Subareas ----------------------------------------------------------------------- Bandyopadhyay et al. Systematic identification of functional orthologs based on protein network comparison. Genome Research 16 (2006), pp. 428-435. Li et al. OrthoMCL: Identification of Ortholog Groups for Eukaryotic Genomes. Genome Research 13 (2003), pp. 2178-2189. Remm et al. Automatic Clustering of Orthologs and In-paralogs from Pairwise Species Comparisons. J. Molecular Biology (2001) 314, pp. 1041-1052. Sharan et al. Conserved patterns of protein interaction in multiple species. PNAS, February 8, 2005, 1974-1979. Sharan and Ideker. Modeling cellular machinery through biological network comparison. Nature Biotechnology 24 (2006), 427-433. Singh et al. Global alignment of multiple protein interaction networks with application to functional orthology detection. PNAS, September 2, 2008, pp. 12763-12768. Yosef et al. Improved Network-based Identification of Protein Orthologs. Bioinformatics Vol. 24 ECCB 2008, pp. i200-i206.

1 0

A Halderman FPO
by Melissa Lawson 04 May '09

04 May '09

Alex Halderman will present his FPO on Friday May 8 at 8AM in Room 402. The members of his committee are: Ed Felten, advisor; Andrew Appel and Avi Rubin (Johns Hopkins), readers; Brian Kernighan and Adam Finkelstein, nonreaders. A copy of his thesis, "Investigating Security Failures and their Causes: An Analytic Approach to Computer Security", is on display in Room 310. Everyone is invited to attend his talk.

1 0

J Terrace general exam
by Melissa Lawson 01 May '09

01 May '09

Jeff Terrace will present his research seminar/general exam on Friday May 8 at 2PM in Room 302 (note room). The members of his committee are: Mike Freedman, advisor, Jennifer Rexford, and Vivek Pai. 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: Massive storage systems typically replicate and partition data over many potentially-faulty components to provide both reliability and scalability. Yet many commercially- deployed systems, especially those designed for inter- active use by customers, sacrifice stronger consistency properties in the desire for greater availability and higher throughput. I will present the design, implementation, and evaluation of CRAQ, a distributed object-storage system that challenges this inflexible tradeoff. The basic approach, an improvement on Chain Replication, maintains strong consistency while greatly improving read throughput. By distributing load across all object replicas, CRAQ scales linearly with chain size without increasing consistency coordination. At the same time, it exposes non- committed operations for weaker consistency guarantees when this suffices for some applications, which is especially useful under periods of high system churn. I will explore additional design and implementation considerations for geo-replicated CRAQ storage across multiple datacenters to provide locality-optimized operations. I will also discuss multi-object atomic updates and multicast optimizations for large-object updates. Reading List: [1] G. DeCandia, D. Hastorun, M. Jampani, G. Kakula-pati, A. Lak-shman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon’s highly available key-value store. [2] R. Guerraoui, D. Kostic, R. R. Levy, and V. Quma. A high throughput atomic storage algorithm. [3] R. van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. [4] I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup protocol for Internet applications. [5] M. Burrows. The Chubby lock service for loosely-coupled distributed systems. [6] S. Ghemawat, H. Gobioff, and S.-T. Leung. The google ?le system. [7] M. Castro and B. Liskov. Practical byzantine fault tolerance. [8] B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS:Yahoo!'s Hosted Data Serving Platform. [9] M. K. Aguilera, A. Merchant, M. Shah, A. Veitch, and C. Karamanolis. Sinfonia: a new paradigm for building scalable distributed systems. In Proc. SOSP, Oct. 2007. [10] K. P. Berman. Reliable Distributed Systems, Chapters 13-19.

1 0