January 2015 - talks - lists.cs.princeton.edu

Colloquium Speaker Simon Peter, Mon Feb 23, 12:30pm
by Nicole E. Wagenblast 17 Feb '15

17 Feb '15

Colloquium Speaker Simon Peter, University of Washington Monday, February 23, 12:30pm Computer Science 105 Building an Operating System for the Data Center Data centers run a range of important applications with ever increasing performance demands, from cloud and server computing to Big Data and eScience. However, the scaling of CPU frequency has stalled in recent years, leading to hardware architectures that no longer transparently scale software performance. Two trends stand out: 1) Instead of frequency, hardware architectures increase the number of CPU cores, leaving complex memory system performance and CPU scheduling tradeoffs exposed to software. 2) Network and storage I/O performance continues to improve, but without matching improvements in CPU frequency. Software thus faces ever increasing I/O efficiency demands. In my research, I address how operating systems (OSes) can handle these growing complexity and performance pressures to avoid becoming the limiting factor to performance. I first explain how current OS architecture is already inadequate to address these trends, limiting application performance. I then present how the OS can be redesigned to eliminate the performance limitations without compromising on existing features or application compatibility. I finish with an outlook on how these hardware trends affect software in the future and present ideas to address them. Simon is a postdoctoral research associate at the University of Washington, where he leads research in operating systems and networks. His postdoctoral advisors are Tom Anderson and Arvind Krishnamurthy. Simon received a Ph.D. in Computer Science from ETH Zurich in 2012 and an MSc in Computer Science from the Carl-von-Ossietzky University Oldenburg, Germany in 2006. Simon's research focus is on data center performance issues. For his work on the Arrakis high I/O performance operating system, he received the Jay Lepreau best paper award (2014) and the Madrona prize (2014). Previously, Simon has worked on the Barrelfish multicore operating system and conducted further award-winning systems research at various locations, including MSR Silicon Valley, MSR Cambridge, Intel Labs Germany, UC Riverside, and the NSF.

1 1

Colloquium Speaker Omer Reingold Wed Feb 4, 12:30pm
by Nicole E. Wagenblast 29 Jan '15

29 Jan '15

Colloquium Speaker Randomness Vs. Memory: A Treasure(s) Hunt Omer Reingold, Weizmann Institute of Science Wednesday, February 4, 12:30pm Computer Science 105 Randomness Vs. Memory: A Treasure(s) Hunt Randomness plays a major role in computation, allowing the execution of tasks that would otherwise be impossible or prohibitively inefficient. Yet the relative power of randomness compared with other resources of computation is mostly unresolved. In this talk we will address the tradeoff between memory and randomness. Namely, can randomness signiﬁcantly reduce the amount of memory needed for algorithmic tasks? This is one of the central problems in Computational Complexity and its study is tied with the study of pseudorandom generators that fool memory-bounded algorithms (i.e. combinatorial objects that look random to small-memory distinguishers). There are many exciting questions on the path towards resolving the randomness vs memory problem. In this talk we will focus on two such areas of research. First, we will discuss small memory algorithms for graph connectivity as well as pseudorandom walks, which we will relate to the general problem of randomness vs. memory. Then we will describe pseudorandom families of hash functions for data structures that are simultaneously small and efficient (with applications to load balancing, the two-choice paradigm, cuckoo hashing, and min-hashing). We will relate such families to progress on more traditional pseudorandom objects such as epsilon-bias sequences and functions with limited independence. Omer Reingold is a Professor of Computer Science at the Weizmann Institute of Science and a Visiting Professor at Stanford University. Past positions include Microsoft Research, the Institute for Advanced Study in Princeton, NJ, and AT&T Labs. His research is in the Foundations of Computer Science and most notably in Computational Complexity and the Foundations of Cryptography with emphasis on randomness, derandomization and explicit combinatorial constructions. He is an ACM Fellow and among his distinctions are the 2005 Grace Murray Hopper Award and the 2009 Gödel Prize.

1 0

Joshua Kroll's PreFPO will take place Feb 3, 2015 at 2pm in CITP conference room (Sherrerd 306)
by Nicki Gotsis 28 Jan '15

28 Jan '15

Joshua Kroll will present his PreFPO on Feb 3, 2015 at 2pm in CITP conference room (Sherrerd 306). The members of his committee are: Ed Felten (advisor); Matt Green (Johns Hopkins University) and Arvind Narayanan (readers); Andrew Appel and Nick Feamster (nonreaders). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Accountable Algorithms Abstract: Important decisions about people are increasingly made by algorithms: Votes are counted; voter rolls are purged; financial aid decisions are made; taxpayers are chosen for audits; air travelers are selected for search; credit eligibility decisions are made. Citizens, and society as a whole, have an interest in making these processes more transparent. Yet the full basis for these decisions is rarely available to affected people: the algorithm or some inputs may be secret; or the implementation may be secret; or the process may not be precisely described. A person who suspects the process went wrong has little recourse. And an oversight authority who wants to ensure that decisions are made according to an acceptable policy has little assurance that proffered decision rules match decisions for actual users. Traditionally, Computer Science addresses these problems by demanding a specification of the desired behavior, which can then be enforced or verified. But this model is poorly suited to real-world oversight tasks, where the specification might be complicated or might not be known in advance. For example, laws are often ambiguous precisely because it would be politically (and practically) infeasible to give a precise specification of their meaning. Instead, people do their best to approximate what they believe the law will allow and disputes about what is actually acceptable happen after-the-fact via expensive investigation and adjudication (e.g. in a court or legislature). As a result, actual oversight, in which real decisions are reviewed for their correctness, fairness, or faithfulness to a rule happens only rarely, if at all. Further, Computer Science often sees rules as self-enforcing: the mere fact that an automated check fails is sufficient to demonstrate that some choice was invalid. However, like all rules, automated rules (even those implemented by cryptography) are just the intentions of a system designer and only bear relevance to the extent that people will actually follow them, either due to internalized incentives or the external threat of punishment. In this thesis, we present a novel approach to relating the tools of technology to the problem of overseeing decision making processes. Our methods use the tools of computer science to cryptographically ensure the technical properties that can be proven, while providing information necessary for a political, legal, or social oversight process to operate effectively. First, we present a system for the accountable execution of legal warrants, in which the decision by a judge to allow an investigator access to private or sensitive records is realized cryptographically, so that the investigator's access to sensitive information is limited to only that information which the judge has explicitly allowed (and this can be confirmed by a disinterested third party). This system is an example of the current style of technical systems for accountability: a well-defined policy, specified in advance, is operationalized with technical tools. However, our construction does not just enforce the policy, but can convince others that the policy is being enforced correctly. Second, we present accountable algorithms, unifying the tools of zero-knowledge computational integrity with cryptographic commitments to design processes that admit meaningful after-the-fact oversight, consistent with the norm in law and policy. Accountable algorithms can attest to the valid operation of a decision policy even when all or part of that policy is kept secret.

1 0

Annie Edmundson will present her General Exam on January 21st, 2015 at 2pm in 302
by Nicki Gotsis 15 Jan '15

15 Jan '15

Annie Edmundson will present her General Exam on January 21st, 2015 at 2pm in 302. The members of her committee are Ed Felten, Arvind Narayanan and Cynthia Sturton (UNC-Chapel Hill). 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 are attached. Abstract: Malicious hardware provides an attacker a greater advantage than software-based attacks because it gives an attacker control over the entire software stack while providing a smaller chance of detection and prevention. The supply chain process for devices is extremely hard to secure in order to provide trusted microelectronic components; current methods for malicious circuit detection at design time usually look for circuitry that is never or rarely used. These methods include dynamic analysis during verification testing and boolean function analysis on a gate-level netlist. This work shows how to defeat the state-of-the-art algorithms in design time hardware trojan detection. We have implemented a backdoor in the LEON3 processor, which implements the SPARC V8 ISA; the malicious backdoor will allow a user-level program to enter supervisor mode with a specific sequence of instructions. We will also discuss fundamental problems of trojan detection, as well as possible areas for improvement. Reading List: Textbooks: 1. Anderson, Ross. Security engineering. John Wiley & Sons, 2008. 2. Harris, David Money, and Sarah L. Harris. Digital design and computer architecture. Elsevier, 2013. Chapters 1-5, 6.5, 6.6, 7.5, 7.6 Papers: 1. Agrawal, Dakshi, Selcuk Baktir, Deniz Karakoyunlu, Pankaj Rohatgi, and Berk Sunar. "Trojan detection using IC fingerprinting." In Security and Privacy, 2007. SP'07. IEEE Symposium on, pp. 296-310. IEEE, 2007. 2. Bilzor, Michael, Ted Huffmire, Cynthia Irvine, and Tim Levin. "Security checkers: Detecting processor malicious inclusions at runtime." In Hardware-Oriented Security and Trust (HOST), 2011 IEEE International Symposium on, pp. 34-39. IEEE, 2011. 3. Hicks, Matthew, Murph Finnicum, Samuel T. King, Milo Martin, and Jonathan M. Smith. "Overcoming an untrusted computing base: Detecting and removing malicious hardware automatically." In Security and Privacy (SP), 2010 IEEE Symposium on, pp. 159-172. IEEE, 2010. 4. King, Samuel T., Joseph Tucek, Anthony Cozzie, Chris Grier, Weihang Jiang, and Yuanyuan Zhou. "Designing and Implementing Malicious Hardware." LEET 8 (2008): 1-8. 5. Sturton, Cynthia, Matthew Hicks, David Wagner, and Samuel T. King. "Defeating UCI: Building stealthy and malicious hardware." In Security and Privacy (SP), 2011 IEEE Symposium on, pp. 64-77. IEEE, 2011. 6. Waksman, Adam, and Simha Sethumadhavan. "Silencing hardware backdoors." In Security and Privacy (SP), 2011 IEEE Symposium on, pp. 49-63. IEEE, 2011. 7. Waksman, Adam, and Simha Sethumadhavan. "Tamper evident microprocessors." In Security and Privacy (SP), 2010 IEEE Symposium on, pp. 173-188. IEEE, 2010. 8. Waksman, Adam, Matthew Suozzo, and Simha Sethumadhavan. "FANCI: identification of stealthy malicious logic using boolean functional analysis." In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pp. 697-708. ACM, 2013. 9. Zhang, Jie, Feng Yuan, Lingxiao Wei, Zelong Sun, and Qiang Xu. "VeriTrust: verification for hardware trust." In Proceedings of the 50th Annual Design Automation Conference, p. 61. ACM, 2013. 10. Zhang, Jie, Feng Yuan, and Qiang Xu. "DeTrust: Defeating hardware trust verification with stealthy implicitly-triggered hardware Trojans." In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 153-166. ACM, 2014.

1 0

Colloquium Speaker Adam Wierman, Today, 11am
by Nicole E. Wagenblast 15 Jan '15

15 Jan '15

Colloquium Speaker Adam Wierman, CalTech Data Centers, Energy, and Online Optimization Thursday, January 15, 11:00am Computer Science 105 This talk will tell two stories, one about designing sustainable data centers and one about the underlying algorithmic challenges, which fall into the context of online convex optimization. Story 1: The typical message surrounding data centers and energy is an extremely negative one: Data centers are energy hogs. This message is pervasive in both the popular press and academia, and it certainly rings true. However, the view of data centers as energy hogs is too simplistic. One goal of this talk is to highlight that, yes, data centers use a lot of energy, but data centers can also be a huge benefit in terms of integrating renewable energy into the grid and thus play a crucial role in improving the sustainability of our energy landscape. In particular, I will highlight a powerful alternative view: data centers as demand response opportunities. Story 2: Typically in online convex optimization it is enough to exhibit an algorithm with low (sub-linear) regret, which implies that the algorithm can match the performance of the best static solution in retrospect. However, what if one additionally wants to maintain performance that is nearly as good as the dynamic optimal, i.e., a good competitive ratio? In this talk, I'll highlight that it is impossible for an online algorithm to simultaneously achieve these goals. Luckily though, in practical settings (like data centers), noisy predictions about the future are often available, and I will show that, under a general model of prediction noise, even very limited predictions about the future are enough to overcome the impossibility result. Adam Wierman is a Professor in the Department of Computing and Mathematical Sciences at the California Institute of Technology, where he is a founding member of the Rigorous Systems Research Group (RSRG) and maintains a popular blog called Rigor + Relevance. His research interests center around resource allocation and scheduling decisions in computer systems and services. He received the 2011 ACM SIGMETRICS Rising Star award, the 2014 IEEE Communications Society William R. Bennett Prize, and has been coauthor on papers that received of best paper awards at ACM SIGMETRICS, IEEE INFOCOM, IFIP Performance (twice), IEEE Green Computing Conference, IEEE Power & Energy Society General Meeting, and ACM GREENMETRICS.

1 0

Santiago Cuellar will present his General Exam on Wednesday, January 21st, 2015 in Room 402 at 2pm.
by Nicki Gotsis 14 Jan '15

14 Jan '15

Santiago Cuellar will present his General Exam on Wednesday, January 21st, 2015 in Room 402 at 2pm. The members of his committee are Andrew W. Appel, David Walker, and Aarti Gupta. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His/her abstract and reading list follow below. ================================================ Abstract: The first verified separate compiler for C, Compositional CompCert, was recently introduced with an operational model supporting language-independent linking and machine-checked proofs of vertical and horizontal composition, strengthening Leroy’s original CompCert proofs. The key techniques for its verification are structured simulations: logical relations between runtime states that enforce safety invariants in the presence of compiler-managed memory regions (private) and addressable portions of the stack frames that might be leaked to foreign modules through external function calls (public). However, the invariants are too strict to allow merging of stack frame as needed, for example, in function inlining optimizations. Moreover, changing the simulations is challenging since they strike a delicate balance that satisfies relies and guarantees among the compiled modules. In this work we present a refinement of the structured simulations that admits a larger number of compiler transformations (e.g. Function inlining) while maintaining compatibility with the operational model and the semantics preservation proof of the full compiler. The relaxation of the simulation works together with a strengthening of the proof for the composition of compiler phases (transitivity). The development has been written and verified in the proof assistant Coq. ======================================================== Reading List: Text books: * A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998 * Part I Fundamentals of Compilation * 13. Garbage Collection * 15. Functional Programming Languages (?) * 17. Dataflow Analysis * 19. Static Single-Assignment Form B. Pierce. Types and Programming Languages. 2002. * Part I Untyped Systems * Part II Simple Types * Part IV Recursive Types * Part V Polymorphism * 22. Type Reconstruction * 23. Universal Types * 24. Existencial Types * 25. An ML Implementation of system F Papers * [A. W. Appel] VeriSmall: Veriﬁed Smallfoot Shape Analysis. In First International Conf. on Certiﬁed Programs and Proofs Dec. 2011 * *[L. Beringer, G. Stewart, and A. W. Appel] Verified compilation for shared-memory C. In Esop’ 14: The 23rd European Symposium on Programming, 2014. * *[Leroy 2009] X. Leroy. Formal verification of a realistic compiler. Communications of the ACM, 52(7):107–115, 2009. * *[James T. Perconti and Amal Ahmed] Verifying an Open Compiler Using Multi-Language Semantics. Programming Languages and Systems 2014 * [Reynolds 2002] J.C. Reynolds. Separation Logic: a Logic for Shared Mutable Data Structures. In LICS’02: Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, pages 55 - 74, 2002. * [Lerner 2003] S. Lerner, T. Millstein, and C. Chambers. Automatically Proving the Correctness of Compiler Optimizations. In PLDI’03: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, 2003. * [Leroy and Blazy 2008] X. Leroy and S. Blazy. Formal verification of a C-like memory model and its uses for verifying program transformations. J. Automated Reasoning, 41(1):1–31, 2008. * [G. Morrisett and D. Walker] From System F to Typed Assembly Language

1 0

Colloquium Speaker Adam Wierman, Thursday, Jan 15, 11am
by Nicole E. Wagenblast 14 Jan '15

14 Jan '15

Colloquium Speaker Adam Wierman, CalTech Data Centers, Energy, and Online Optimization Thursday, January 15, 11:00am Computer Science 105 This talk will tell two stories, one about designing sustainable data centers and one about the underlying algorithmic challenges, which fall into the context of online convex optimization. Story 1: The typical message surrounding data centers and energy is an extremely negative one: Data centers are energy hogs. This message is pervasive in both the popular press and academia, and it certainly rings true. However, the view of data centers as energy hogs is too simplistic. One goal of this talk is to highlight that, yes, data centers use a lot of energy, but data centers can also be a huge benefit in terms of integrating renewable energy into the grid and thus play a crucial role in improving the sustainability of our energy landscape. In particular, I will highlight a powerful alternative view: data centers as demand response opportunities. Story 2: Typically in online convex optimization it is enough to exhibit an algorithm with low (sub-linear) regret, which implies that the algorithm can match the performance of the best static solution in retrospect. However, what if one additionally wants to maintain performance that is nearly as good as the dynamic optimal, i.e., a good competitive ratio? In this talk, I'll highlight that it is impossible for an online algorithm to simultaneously achieve these goals. Luckily though, in practical settings (like data centers), noisy predictions about the future are often available, and I will show that, under a general model of prediction noise, even very limited predictions about the future are enough to overcome the impossibility result. Adam Wierman is a Professor in the Department of Computing and Mathematical Sciences at the California Institute of Technology, where he is a founding member of the Rigorous Systems Research Group (RSRG) and maintains a popular blog called Rigor + Relevance. His research interests center around resource allocation and scheduling decisions in computer systems and services. He received the 2011 ACM SIGMETRICS Rising Star award, the 2014 IEEE Communications Society William R. Bennett Prize, and has been coauthor on papers that received of best paper awards at ACM SIGMETRICS, IEEE INFOCOM, IFIP Performance (twice), IEEE Green Computing Conference, IEEE Power & Energy Society General Meeting, and ACM GREENMETRICS.

1 0

1-3pm Thu Jan 15 poster session for COS 561 (grad networks) in the Friend Convocation Room
by Jennifer Rexford 14 Jan '15

14 Jan '15

The students in COS 561 (graduate computer networks) are having a poster session to present their final course projects. The poster session will be 1-3pm Thursday January 15 in the Friend Convocation Room. The 25 projects will be divided into two one-hour periods, each including about half of the posters. We'll have snacks and beverages. Everyone is welcome! The project titles and authors are listed below. -- Jen FIRST HOUR (1-2pm) Managing Fairness in Equilibrium Strategies for Routing Among Selfish Nodes in an Ad Hoc Network Andrew Grasso Global Internet Reachability: A Longitudinal Study Anne Edmundson, Elba Garza, Caroline Trippel Improving the Performance of Path Query in Software Defined Networks Mina Tahmasbi Arashloo Proxy Rotation with Bitcoin Micropayments Miles Carlsten, Harry Kalodner, Paul Ellenbogen TIP: An IP Protocol for Detecting BGP Hijacking Attacks Collin Stedman Ravana: Transparent Controller Fault Tolerance in Software-Defined Networks Haoyu Zhang Latency Equalized Routing for Interactive Networks Heemin Seog and Andrew Tran Imagining a Clock-Synchronized Internet Gregory Owen and Jonathan Frankle Statistics Query Support for CoVisor Jennifer Gossels Detecting BGP Man-in-the-Middle Attacks via Control Plane Anomaly Detection Cornellius K. Metto, Laura M. Roberts, Elena Sizikova Fast BGP Convergence with the Supercharged Router: Electrifying Traditional Routers with SDN Michael Alan Chang Compressing Cached Rules in Software-Defined Networks Yatin A. Manerkar, Adi Fuchs, Alexey Lavrov SECOND HOUR (2-3pm) Upgrading HTTPS in Mid-Air: An Empirical Study of Strict Transport Security and Key Pinning Michael Kranch Prediction Based Mechanism for efficient scheduling of Cellular Data usage Themistoklis Melissaris, Nayana Prasad Nagendra Towards Temporal Network Synthesis Ryan Beckett, Qinxiang Cao, Olivier Savary Bélanger Multi-Network Cellular Access Parishad Karimi SDN-Enabled IPv4 Multicast Protocol Design Robert Macdavid, Sergiy Popovych, Hansen Zhang A Visualization Environment for Network Information in Pyretic Nora Coler, Ruth Dannenfelser, and Nevin Li Inter-domain path diversity through virtual peering Shreyasee Mukherjee MITM Detection with P2P Networks Steven Englehardt, Steven Goldfeder, Maciej Halber, Peter Zimmerman Evaluating Path Queries in Software-Defined Networks with Different Forwarding Policies Violeta Ilieva Dynamic Service Chaining Tengyu Ma, Amy Tai, Kelvin Zou Customizable Adaptive Streaming over Cellular Network Yichen Chen, Yixin Sun Exploring Scalability in Hierarchical SDN Controllers Disney Y. Lam Towards remote music collaboration: forecasting mallet motion via networks Huiwen Chang, Zeyu Jin and Shuran Song

1 0

Elba Garza will present her Generals on Monday, January 19, 2015 at 8:30 am in Rm 401
by Nicki Gotsis 12 Jan '15

12 Jan '15

Elba Garza will present her Generals on Monday, January 19, 2015 at 8:30 am in Rm 401. The members of her committee are David August, Margaret Martonosi, Kelly Shaw (University of Richmond). Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His/her abstract and reading list follow below. Abstract The emerging popularity of heterogeneous architectures results in a necessary and complex selection of runtime hardware/software parameters. As these heterogeneous systems have grown to offload computation to graphics processing units (GPUs), various Application-specific integrated circuits (ASICs) and other compute units, there is a higher need to optimize these units’ software and hardware settings to reach better power, performance, and area goals. Exhaustive exploration techniques are impractical since the design spaces grow exponentially with the addition of new parameters. Design spaces can easily reach thousands or millions of configurations to simulate or test. Manual and inference-based information can be flawed due to individual knowledge and bias, which may lead to unsearched design areas. Using statistical learning techniques, we have been able to optimize design space exploration for parameters of heterogeneous architecture components such as GPUs and Accelerator ASICs. These techniques allow for efficient and tractable design space assessment and can output optimal or near-optimal parameter settings for given applications automatically. Reading List [Cas+10] C. Cascaval et al. “A taxonomy of accelerator architectures and their programming models”. In: IBM Journal of Research and Development 54.5 (Sept. 2010), 5:1–5:10. issn: 0018-8646. doi: 10. 1147/JRD.2010.2059721. [Con+14] Jason Cong et al. “Accelerator-Rich Architectures: Opportunities and Progresses”. In: Proceedings of the 51st Annual Design Automation Conference. DAC ’14. San Francisco, CA, USA: ACM, 2014, 180:1–180:6. isbn: 978-1-4503-2730-5. doi: 10 . 1145 / 2593069 . 2596667. url: http://doi.acm.org/10.1145/2593069.2596667. [Esm+11] Hadi Esmaeilzadeh et al. “Dark Silicon and the End of Multicore Scaling”. In: Proceedings of the 38th Annual International Symposium on Computer Architecture. ISCA ’11. San Jose, California, USA: ACM, 2011, pp. 365–376. isbn: 978-1-4503-0472-6. doi: 10. 1145/2000064.2000108. url: http://doi.acm.org/10.1145/ 2000064.2000108. [Lyo+12] Michael J. Lyons et al. “The Accelerator Store: A Shared Memory Framework for Accelerator-based Systems”. In: ACM Trans. Archit. Code Optim. 8.4 (Jan. 2012), 48:1–48:22. issn: 1544-3566. doi: 10. 1145/2086696.2086727. url: http://doi.acm.org/10.1145/ 2086696.2086727. [Sha+14] Yakun Sophia Shao et al. “Aladdin: A Pre-RTL, Power-performance Accelerator Simulator Enabling Large Design Space Exploration of Customized Architectures”. In: Proceeding of the 41st Annual International Symposium on Computer Architecuture. ISCA ’14. Minneapolis, Minnesota, USA: IEEE Press, 2014, pp. 97–108. isbn: 1lba Garza January 19, 2015 978-1-4799-4394-4. url: http://dl.acm.org/citation.cfm?id= 2665671.2665689. [Ham+10] Rehan Hameed et al. “Understanding Sources of Inefficiency in General-purpose Chips”. In: Proceedings of the 37th Annual International Symposium on Computer Architecture. ISCA ’10. SaintMalo, France: ACM, 2010, pp. 37–47. isbn: 978-1-4503-0053-7. doi: 10.1145/1815961.1815968. url: http://doi.acm.org/10.1145/ 1815961.1815968. [JSM12] Wenhao Jia, Kelly A. Shaw, and Margaret Martonosi. “Stargazer: Automated Regression-based GPU Design Space Exploration”. In: Proceedings of the 2012 IEEE International Symposium on Performance Analysis of Systems & Software. ISPASS ’12. Washington, DC, USA: IEEE Computer Society, 2012, pp. 2–13. isbn: 978-1- 4673-1143-4. doi: 10 . 1109 / ISPASS . 2012 . 6189201. url: http : //dx.doi.org/10.1109/ISPASS.2012.6189201. [JSM13] Wenhao Jia, Kelly A. Shaw, and Margaret Martonosi. “Starchart: Hardware and Software Optimization Using Recursive Partitioning Regression Trees”. In: Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques. PACT ’13. Edinburgh, Scotland, UK: IEEE Press, 2013, pp. 257– 268. isbn: 978-1-4799-1021-2. url: http://dl.acm.org/citation. cfm?id=2523721.2523757. [JVT06a] P. J. Joseph, K. Vaswani, and Matthew J. Thazhuthaveetil. “Construction and use of linear regression models for processor performance analysis”. In: High-Performance Computer Architecture, 2006. The Twelfth International Symposium on. Feb. 2006, pp. 99– 108. doi: 10.1109/HPCA.2006.1598116. [JVT06b] P. J. Joseph, Kapil Vaswani, and Matthew J. Thazhuthaveetil. “A Predictive Performance Model for Superscalar Processors”. In: Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture. MICRO 39. Washington, DC, USA: IEEE Computer Society, 2006, pp. 161–170. isbn: 0-7695-2732-9. doi: 10.1109/MICRO.2006.6. url: http://dx.doi.org/10.1109/ MICRO.2006.6. [LB06] Benjamin C. Lee and David M. Brooks. “Accurate and Efficient Regression Modeling for Microarchitectural Performance and Power Prediction”. In: SIGPLAN Not. 41.11 (Oct. 2006), pp. 185–194. issn: 0362-1340. doi: 10 . 1145 / 1168918 . 1168881. url: http : //doi.acm.org/10.1145/1168918.1168881. 2lba Garza January 19, 2015 Book List [HP12] J.L. Hennessy and D.A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann. Morgan Kaufmann/Elsevier, 2012. isbn: 9780123838728. Nicki Gotsis Graduate Coordinator Room 310, Computer Science (609) 258-5387 ngotsis(a)cs.princeton.edu

1 0

Colloquium speaker: Ben Raphael, Today, 4:30pm
by Nicole E. Wagenblast 12 Jan '15

12 Jan '15

Colloquium Speaker Ben Raphael, Brown University Monday, January 12, 4:30pm Computer Science 105 Understanding the molecular alterations that cause cancer is one of the greatest challenges in biology and medicine. Recent advances in DNA sequencing technology now enable large-scale measurement of mutations in cancer genomes and provide an unprecedented opportunity to address this challenge. However, translating this information into deeper insight about the mutational process that drives cancer demands novel computational approaches. In this talk, I will describe algorithms that we have developed to address key problems in cancer genomics. First, I will discuss algorithms that deconvolve DNA sequencing data from a single tumor and determine subpopulations of cancer cells harboring different mutations. These algorithms exploit integrality constraints on copy number aberrations and phylogenetic tree constraints that relate subpopulations. Next, I will describe algorithms to identify combinations of mutations that perturb cellular signaling and regulatory networks. One algorithm employs a heat diffusion process to identify subnetworks of a genome-scale interaction network that are recurrently mutated across samples. A second algorithm finds combinations of mutations that optimize a measure of mutual exclusivity across samples. I will illustrate applications of these approaches to multiple cancer types in The Cancer Genome Atlas (TCGA), including a recent Pan-Cancer study of >3000 samples from 12 cancer types. Ben Raphael is an Associate Professor in the Department of Computer Science and Director of the Center for Computational Molecular Biology (CCMB) at Brown University. His research focuses on the design of algorithms for genome sequencing and interpretation. Recent interests include structural variation in human and cancer genomes, and network/pathway analysis of genetic variants. He received an S.B. in Mathematics from MIT, a Ph.D. in Mathematics from the University of California, San Diego (UCSD), and completed postdoctoral training in Bioinformatics and Computer Science at UCSD. He is the recipient of an NSF CAREER award, a Career Award from the Burroughs Wellcome Fund, and a Sloan Research Fellowship.

1 0