December 2016 - talks - lists.cs.princeton.edu

Colloquium Speaker: Lior Pachter, Today, 12:30pm
by Nicole E. Wagenblast 13 Dec '16

13 Dec '16

Colloquium Speaker Lior Pachter, University of California, Berkeley Tuesday, December 13th, 12:30pm Computer Science 105 I will survey a number of recently developed sequencing based assays for functional genomics, and discuss a number of fundamental statistical and computational ideas that make allow for extracting genomic information from sequencing reads. Examples will be drawn from assays such as RNA-Seq, DMS/SHAPE-Seq, PseudoSeq and iCLIP. I will be discussing work that is joint with Sharon Aviran, Nicolas Bray, Shannon Hateley, Bo Li, Shannon McCurdy, Páll Melsted, Vasilis Ntranos, Harold Pimentel, Akshay Tambe and Lynn Yi. I was born in Ramat Gan, Israel, and grew up in Pretoria, South Africa where I attended Pretoria Boys High School. After receiving a B.S. in Mathematics from Caltech in 1994, I left for MIT where I was awarded a PhD in applied mathematics in 1999. I then moved to the University of California at Berkeley where I was a postdoctoral researcher (1999-2001), assistant professor (2001-2005), associate professor (2005-2009), and am currently the Raymond and Beverly Sackler professor of computational biology at UC Berkeley and professor of mathematics and molecular and cellular biology with a joint appointment in computer science. My research interests span the mathematical and biological sciences, and I have authored over 100 research articles in the areas of algorithms, combinatorics, comparative genomics, algebraic statistics, molecular biology and evolution. I've been awarded a National Science Foundation CAREER award, a Sloan Research Fellowship, the Miller Professorship, and a Federal Laboratory Consortium award for the successful technology transfer of widely used sequence alignment software developed in my group.

1 0

Fwd: Seminar: Prof. Vijay Nagarajan, U Edinburgh. Dec 12: 4:30pm. CS 402.
by Margaret Martonosi 12 Dec '16

12 Dec '16

HI all- Prof. Vijay Nagarajan from U. Edinburgh is visiting today and giving a computer architecture seminar at 4:30 in CS 402. The details are below. His one-on-one schedule is pretty full at this point, but please let me know if you’d like to be added. thanks, -mrm > Monday Dec 12. 4:30pm. CS 402. > > Title: Semantics-directed Hardware Design for Shared Memory > > Abstract: > > With regard to hardware support for shared-memory concurrency, an > inherent trade-off between programmability and efficiency is presumed. > For instance, the most intuitive memory consistency model, sequential > consistency (SC), is presumed to be too expensive to support; > likewise primitive synchronization instructions such as memory fences > and atomic read-modify writes (RMWs) are costly in current processors; > finally, there are question marks about whether cache coherence > protocols will scale with increasing number of cores. > > In this talk, I will argue that it is indeed possible to provide > hardware support that enhances programmability without sacrificing > efficiency. The key insight is semantics-directed design: hardware > design should be guided by precise formal specifications, instead of > ad-hoc informal ones. > > I will illustrate this idea briefly by first showing how SC can be > enforced efficiently using a novel technique to enforce memory > ordering dubbed conflict ordering. Second, I will show how RMWs can be > implemented efficiently in x86 architectures. Third, and the focus of > this talk will be a scalable approach for cache coherence called > TSO-CC. TSO-CC is a protocol that breaks the traditional > coherence/consistency abstraction, relying on self-invalidation and > acquire detection to satisfy the TSO memory consistency model. After > briefly discussing the verification challenges that ensue, I will > conclude with how I believe semanticists, hardware designers, and > verification experts can work together to create correct and efficient > hardware designs. > > Bio: > > Vijay Nagarajan is an Associate Professor at the University of > Edinburgh. His research interests span computer architecture, > compilers, and systems with a focus on memory consistency models and > cache coherence protocols. Vijay received his PhD from University of > California Riverside and MS from University of Arizona. He is a > recipient of Intel Early Career Faculty Award and a best-paper award > at PACT. > > > Margaret Martonosi > H. T. Adams '35 Professor of Computer Science. > Princeton University ■ mrm(a)princeton.edu ■ http://www.princeton.edu/~mrm > > > >

1 0

Colloquium Speaker: Lior Pachter, Tues Dec 13, 12:30pm- reminder
by Nicole E. Wagenblast 12 Dec '16

12 Dec '16

Colloquium Speaker Lior Pachter, University of California, Berkeley Tuesday, December 13th, 12:30pm Computer Science 105 I will survey a number of recently developed sequencing based assays for functional genomics, and discuss a number of fundamental statistical and computational ideas that make allow for extracting genomic information from sequencing reads. Examples will be drawn from assays such as RNA-Seq, DMS/SHAPE-Seq, PseudoSeq and iCLIP. I will be discussing work that is joint with Sharon Aviran, Nicolas Bray, Shannon Hateley, Bo Li, Shannon McCurdy, Páll Melsted, Vasilis Ntranos, Harold Pimentel, Akshay Tambe and Lynn Yi. I was born in Ramat Gan, Israel, and grew up in Pretoria, South Africa where I attended Pretoria Boys High School. After receiving a B.S. in Mathematics from Caltech in 1994, I left for MIT where I was awarded a PhD in applied mathematics in 1999. I then moved to the University of California at Berkeley where I was a postdoctoral researcher (1999-2001), assistant professor (2001-2005), associate professor (2005-2009), and am currently the Raymond and Beverly Sackler professor of computational biology at UC Berkeley and professor of mathematics and molecular and cellular biology with a joint appointment in computer science. My research interests span the mathematical and biological sciences, and I have authored over 100 research articles in the areas of algorithms, combinatorics, comparative genomics, algebraic statistics, molecular biology and evolution. I've been awarded a National Science Foundation CAREER award, a Sloan Research Fellowship, the Miller Professorship, and a Federal Laboratory Consortium award for the successful technology transfer of widely used sequence alignment software developed in my group.

1 0

Colloquium Speaker: Lior Pachter, Tues Dec 13, 12:30pm
by Nicole E. Wagenblast 07 Dec '16

07 Dec '16

Colloquium Speaker Lior Pachter, University of California, Berkeley Tuesday, December 13th, 12:30pm Computer Science 105 I will survey a number of recently developed sequencing based assays for functional genomics, and discuss a number of fundamental statistical and computational ideas that make allow for extracting genomic information from sequencing reads. Examples will be drawn from assays such as RNA-Seq, DMS/SHAPE-Seq, PseudoSeq and iCLIP. I will be discussing work that is joint with Sharon Aviran, Nicolas Bray, Shannon Hateley, Bo Li, Shannon McCurdy, Páll Melsted, Vasilis Ntranos, Harold Pimentel, Akshay Tambe and Lynn Yi. I was born in Ramat Gan, Israel, and grew up in Pretoria, South Africa where I attended Pretoria Boys High School. After receiving a B.S. in Mathematics from Caltech in 1994, I left for MIT where I was awarded a PhD in applied mathematics in 1999. I then moved to the University of California at Berkeley where I was a postdoctoral researcher (1999-2001), assistant professor (2001-2005), associate professor (2005-2009), and am currently the Raymond and Beverly Sackler professor of computational biology at UC Berkeley and professor of mathematics and molecular and cellular biology with a joint appointment in computer science. My research interests span the mathematical and biological sciences, and I have authored over 100 research articles in the areas of algorithms, combinatorics, comparative genomics, algebraic statistics, molecular biology and evolution. I've been awarded a National Science Foundation CAREER award, a Sloan Research Fellowship, the Miller Professorship, and a Federal Laboratory Consortium award for the successful technology transfer of widely used sequence alignment software developed in my group.

1 0

*Location Change* Colloquium Speaker: Gala Yadgar, TODAY, 4:30pm--Room 402
by Nicole E. Wagenblast 07 Dec '16

07 Dec '16

Colloquium Speaker Dr. Gala Yadgar , from Technion Institute Wednesday, December 7, 2016 - 4:30pm Computer Science 402 The devil is in the details: on the real costs and benefits of WOM codes for Flash NAND flash, used in modern SSDs, is a write-once medium, where each memory cell must be erased prior to writing. The lifetime of an SSD is limited by the number of erasures allowed on each cell. Thus, minimizing erasures is a key objective in SSD design. A promising approach to eliminate erasures and extend SSD lifetime is to use write-once memory (WOM) codes, designed to accommodate additional writes on write-once media. However, these codes inflate the physically stored data by at least 29%, require an extra read operation before each additional write, and their applicability to MLC and TLC flash is restricted. I will describe the first evaluation of the possible benefit from reusing flash pages with WOM codes on real flash chips and an end-to-end FTL design and implementation. Our results expose a considerable gap between the theoretical benefits of page reuse and those that can be achieved on current state-of-the-art hardware. However, they also lay the ground for promising future improvements. Joint work with Fabio Margaglia, Eitan Yaakobi, Yue Li, Assaf Schuster and Andre Brinkmann.

1 0

ORFE Colloquium: David Shmoys '81 Today 12/6 4:30pm, 101 Sherrerd Hall
by Nicole E. Wagenblast 06 Dec '16

06 Dec '16

* Smarter Tools for (Citi)Bike Sharing David Shmoys '81, Cornell University Tue Dec 6 2016 4:30 PM Sherrerd Hall 101 ABSTRACT: New York launched the largest bike-sharing system in North America in May 2013. We have worked with Citibike, using analytics and optimization to change how they manage the system. Huge rush-hour usage imbalances the system; we answer both of the questions: where should bikes be at the start of a rush hour and how can we mitigate the imbalances that develop? We will survey the analytics we have employed for the former question, where we developed an approach based on continuous-time Markov chains combined with integer programming models to compute daily stocking levels for the bikes, as well as methods employed for optimizing the capacity of the stations. For the question of mitigating the imbalances that result, we will describe both heuristic methods and approximation algorithms that guide both mid-rush hour and overnight rebalancing, as well as for the positioning of corrals, which have been one of the most effective means of creating adaptive capacity in the system. This is joint work with Daniel Freund, Shane Henderson, Nanjing Jian, Ashkan Nourozi-Fard, Eoin O’Mahoney, and Alice Paul. BIO: David Shmoys is the Laibe/Acheson Professor at Cornell University in the School of Operations Research and Information Engineering, and also the Department of Computer Science at Cornell University, and is currently the Director of the School of Operations Research and Information Engineering. Shmoys's research has focused on the design and analysis of efficient algorithms for discrete optimization problems, with applications including scheduling, inventory theory, computational biology, and most recently, on stochastic optimization models and algorithms in computational sustainability. His graduate-level text, The Design of Approximation Algorithms, co-authored with David Williamson, was awarded the 2013 INFORMS Lanchester Prize. He is an INFORMS Fellow, a Fellow of the ACM, a SIAM Fellow, and was an NSF Presidential Young Investigator; he has served on numerous editorial boards, and is currently Editor-in-Chief of Research in the Mathematical Sciences (for theoretical computer science) and an Associate Editor of Mathematics of Operations Research. >

1 0

Colloquium Speaker: Gala Yadgar, Technion Institute, Wed, Dec 7, 4:30pm -reminder
by Nicole E. Wagenblast 06 Dec '16

06 Dec '16

Colloquium Speaker Dr. Gala Yadgar , from Technion Institute Wednesday, December 7, 2016 - 4:30pm Computer Science 105 The devil is in the details: on the real costs and benefits of WOM codes for Flash NAND flash, used in modern SSDs, is a write-once medium, where each memory cell must be erased prior to writing. The lifetime of an SSD is limited by the number of erasures allowed on each cell. Thus, minimizing erasures is a key objective in SSD design. A promising approach to eliminate erasures and extend SSD lifetime is to use write-once memory (WOM) codes, designed to accommodate additional writes on write-once media. However, these codes inflate the physically stored data by at least 29%, require an extra read operation before each additional write, and their applicability to MLC and TLC flash is restricted. I will describe the first evaluation of the possible benefit from reusing flash pages with WOM codes on real flash chips and an end-to-end FTL design and implementation. Our results expose a considerable gap between the theoretical benefits of page reuse and those that can be achieved on current state-of-the-art hardware. However, they also lay the ground for promising future improvements. Joint work with Fabio Margaglia, Eitan Yaakobi, Yue Li, Assaf Schuster and Andre Brinkmann.

1 0

Guangda Hu will present his FPO, "Lower Bounds for Error-Correcting Codes with Local Recovery" on Monday, 12/12/2016 at 2:00pm in CS 302.
by Nicki Gotsis 05 Dec '16

05 Dec '16

Guangda Hu will present his FPO, "Lower Bounds for Error-Correcting Codes with Local Recovery" on Monday, 12/12/2016 at 2:00pm in CS 302. The members of his committee are: Zeev Dvir (adviser), Readers: Sanjeev Arora and Shubhangi Saraf (Rutgers University); Nonreaders: Mark Braverman and Elad Hazan. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follows below. Abstract: Error-correcting codes (ECCs) are ubiquitous in computer science. A common property of ECCs is local recovery, which demands that given a corrupted codeword, a single lost code symbol can be recovered by reading only a small part of the codeword. An intriguing problem is to find the most “efficient” ECCs (e.g., codes with short length, codes over a small alphabet) with certain types of local recovery. Both constructions and lower bounds have been proven in the literature. However, the problem is still largely open. In this thesis, we prove three lower bound results on different types of ECCs with local recovery: Firstly, we propose an approximate version of locally decodable codes (LDCs) and prove lower bounds that are similar to the known ones for traditional LDCs. The concerned approximate LDCs are over real numbers and they support recoveries by querying constant number of codeword symbols. The 2-query case (the bulk of our work) is partially related to the lower bound of constant query LDCs, which is a major open problem. Secondly, we generalize the Sylvester-Gallai (SG) theorem to a subspace version. Generally speaking, the setting of the SG theorem is equivalent to 2-query locally correctable codes (LCCs), and our generalization corresponds to the block version of 2-query LCCs. Thirdly, we consider a realistic storage model that is a unification of several families of codes studied in the literature. We prove negative results for codes that attain the maximal recovering capability under this model. Our lower bound rules out the possibility of constructions of efficient codes for most parameter settings. We will also explore some results in the construction direction in the appendix.

1 0

Soumyadeep Ghosh will present his FPO, "TrustGuard: A Containment Architecture with Verified Output" on Monday, 12/12/2016 at 8am in CS 302.
by Nicki Gotsis 05 Dec '16

05 Dec '16

Soumyadeep Ghosh will present his FPO, "TrustGuard: A Containment Architecture with Verified Output" on Monday, 12/12/2016 at 8am in CS 302. The members of his committee are: David August (adviser), Readers: Andrew Appel and Aarti Gupta; Nonreaders: David Wentzlaff and Simha Sethumadhavan (Columbia University). A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follows below. Abstract: Computers today are so complex and opaque that a user cannot know everything occurring within the system. Most efforts toward computer security have focused on securing software. However, software security techniques implicitly assume correct execution by the underlying system, including the hardware. Securing these systems has been challenging due to their complexity and the proportionate attack surface they present during their design, manufacturing, deployment, and operation. Ultimately, the user’s trust in the system depends on claims made by each party supplying the system’s components. This dissertation presents the Containment Architecture with Verified Output (CAVO) model in recognition of the reality that existing tools and techniques are insufficient to secure complex hardware components in modern computing systems. Rather than attempt to secure each complex hardware component individually, CAVO establishes trust in hardware using a single, simple, separately manufactured component, called the Sentry. The Sentry bridges a physical gap between the untrusted system and its external interfaces and contains the effects of malicious behavior by untrusted system components before the external manifestation of any such effects. Thus, only the Sentry and the physical gap must be secured in order to assure users of the containment of malicious behavior. The simplicity and pluggability of CAVO’s Sentry enable suppliers and consumers to take additional measures to secure it, including formal verification, supervised manufacture, and supply chain diversification. This dissertation also presents TrustGuard—the first prototype CAVO design—to demonstrate the feasibility of the CAVO model. TrustGuard achieves containment by only allowing the communication of correctly executed results of signed software. The Sentry in TrustGuard leverages execution information obtained from the untrusted processor to enable efficient checking of the untrusted system’s work, even when the Sentry itself is simpler and much slower than the untrusted processor. Simulations show that TrustGuard can guarantee containment of malicious hardware components with a geomean of 8.5% decline in the processor’s performance, even when the Sentry operates at half the clock frequency of the complex, untrusted processor.

1 0

Colloquium Speaker: Gala Yadgar, Technion Institute, Wed, Dec 7, 4:30pm
by Nicole E. Wagenblast 02 Dec '16

02 Dec '16

Colloquium Speaker Dr. Gala Yadgar , from Technion Institute Wednesday, December 7, 2016 - 4:30pm Computer Science 105 The devil is in the details: on the real costs and benefits of WOM codes for Flash NAND flash, used in modern SSDs, is a write-once medium, where each memory cell must be erased prior to writing. The lifetime of an SSD is limited by the number of erasures allowed on each cell. Thus, minimizing erasures is a key objective in SSD design. A promising approach to eliminate erasures and extend SSD lifetime is to use write-once memory (WOM) codes, designed to accommodate additional writes on write-once media. However, these codes inflate the physically stored data by at least 29%, require an extra read operation before each additional write, and their applicability to MLC and TLC flash is restricted. I will describe the first evaluation of the possible benefit from reusing flash pages with WOM codes on real flash chips and an end-to-end FTL design and implementation. Our results expose a considerable gap between the theoretical benefits of page reuse and those that can be achieved on current state-of-the-art hardware. However, they also lay the ground for promising future improvements. Joint work with Fabio Margaglia, Eitan Yaakobi, Yue Li, Assaf Schuster and Andre Brinkmann.

1 0