- talks - lists.cs.princeton.edu

Anders Miltner will present his General exam on January 11, 2017 at 1:30pm in CS 302.
by Nicki Gotsis 05 Jan '17

05 Jan '17

Anders Miltner will present his General exam on January 11, 2017 at 1:30pm in CS 302. The members of his committee are David Walker, Zak Kincaid, 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. SYNTHESIZING BIJECTIVE STRING TRANSFORMERS ANDERS MILTNER Bidirectional transformers are groups of functions that convert between data formats. The most common bidirectional transformers are parsers and pretty printers, where a parser converts data from a string representation into a structured representation, and a pretty printer converts data from a structured representation back into a string representation. Other bidirectional transformers convert between data models and GUIs, database views and the underlying tables, and different string formats. Inversion guarantees are usually expected of bidirectional transformers; converting from one data representation and back should not alter the content of the data, beyond the modification of unimportant details like whitespace. Writing these functions in general purpose programming languages requires writing multiple functions and manual reasoning about the invertibility guarantees. Researchers have designed domain specific languages, like Boomerang and biXid, to express bidirectional transformations with a single term, while providing invertibility guarantees. However, coding in these languages requires learning a new paradigm, which has hindered their adoption. We aim to increase the accessibility of one of these languages, Boomerang, by synthesizing the bijective fragment of its programs. Boomerang is a bidirectional language for converting between string representations. The type of a Boomerang program is a pair of regular expressions that specify the format of the source and target data sources. Our program takes two regular expressions and a set of examples as input, and outputs a Boomerang program typed by the input regular expressions, that satisfies the examples. This is done using a method called “type-directed synthesis”, where the types inform the synthesizer how to efficiently search the space of possible programs. Existing work on type-directed synthesis operates on type systems with relatively few isomorphisms between the types. However, each regular expression is equivalent to an infinite number of regular expressions. Synthesis thus requires searching through the equivalent regular expression types as well as through possible terms of the types. Furthermore, the types for complicated data formats are much larger and more complex than the types used in existing work in type-directed synthesis, causing a combinatorial explosion when searching through terms. These issues are resolved through converting the types to a different language with fewer equivalences and treating the user defined types semi-opaquely. We evaluate our procedure on 25 examples taken from Augeas, a program for encoding bidirectional transformations of Linux configuration files, other papers, and microbenchmarks built to highlight the strengths and weaknesses of the program. Our synthesis algorithm is able to synthesize all of these programs in an average of less than half a second. Book : Types and Programming Languages Benjamin Pierce 2002 ISBN 0-262-16209-1 General PL Thesis : Bidirectional Programming Languages Nate Foster 2010 http://www.cs.cornell.edu/~jnfoster/papers/jnfoster-dissertation.pdf Lenses Papers : Combinatorial Sketching for Finite Programs Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Vijay Saraswat, Sanjit Seshia 2006 https://people.csail.mit.edu/asolar/papers/asplos06-final.pdf Sketching, Synthesis Stochastic Superoptimization Eric Schkufza, Rahul Sharma, Alex Aiken 2013 http://theory.stanford.edu/~aiken/publications/papers/asplos13.pdf Stoke, Stochastic Synthesis Dual Syntax for XML Languages Claus Brabrand, Anders Møller, Michael I. Schwartzbach 2005 http://cs.au.dk/~amoeller/papers/xsugar/journal.pdf Bidirectional Programming Application of Theorem Proving to Problem Solving Cordell Green 1969 http://www.ai.sri.com/pubs/files/tn004-green69.pdf Classic Paper, Synthesis Ch 4 (Focusing) of Frank Pfenning's ATP notes Frank Pfenning https://www.cs.cmu.edu/~fp/courses/atp/handouts/ch4-focus.pdf Automated Theorem Proving / Classic Regular Combinators for String Transformations Rajeev Alur, Adam Freilich, Mukund Raghothaman 2014 https://www.cis.upenn.edu/~alur/Lics14.pdf String Transformations A Methodology for LISP Program Construction from Examples Phillip D. Summers 1977 http://dl.acm.org/citation.cfm?id=322002 Classic Paper, Synthesis Type-directed Completion of Partial Expressions Daniel Perelman, Sumit Gulwani, Thomas Ball, Dan Grossman 2012 http://research.microsoft.com/en-us/um/people/sumitg/pubs/pldi12.pdf Synthesis, IDEs Learning Semantic String Transformations from Examples Rishabh Singh, Sumit Gulwani 2012 http://research.microsoft.com/en-us/um/people/sumitg/pubs/semantic.pdf String Transformations Synthesis Synthesis through Unification Rajeev Alur, Pavol Cerny, Arjun Radhakrishna 2015 https://www.seas.upenn.edu/~arjunrad/publications/cav15a.pdf Synthesis

1 0

Yingfei Wang will present her Pre-FPO on Tuesday, January 10, 2017 at 2pm in CS 402
by Nicki Gotsis 03 Jan '17

03 Jan '17

Yingfei Wang will present her Pre-FPO on Tuesday, January 10, 2017 at 2pm in CS 402. The members of her committee are: Warren Powell (adviser); Bernard Chazelle and Mengdi Wang (readers); Szymon Rusinkiewicz and Han Liu (nonreaders). Everyone is invited to attend her talk. Abstract follows below. We consider the problem of sequentially making decisions under uncertainty, exploring the ways where efficient information collection influences and improves decision-making strategies. My thesis work provides a comprehensive set of techniques that span from designing efficient optimal learning algorithms in parallel computing environments, to making decisions under parametric belief models which introduce additional computational hurdles, to finite-time and asymptotic guarantees, with an emphasis on how efficient information collection can expand access, decrease costs and improve quality in health care. Specifically, (1)we offer a new perspective of interpreting ranking and selection problems as adaptive stochastic multi-set maximization problems and deriving the first finite-time bound of the knowledge-gradient. In addition, we introduce the concept of prior-optimality and provide another insight into the performance of the knowledge gradient policy based on the submodular assumption on the value of information. (2) Driven by needs among materials science society, we developed a Nested-Batch-KG policy for sequential experiments when experiments can be conducted in parallel and/or there are multiple tunable parameters which are decided at different stages in the process. (3) Motivated by personalized medicine, we develop knowledge-gradient type policies under Bayesian generalized linear models. Finite time bound and asymptotic convergence are proved. We extend the knowledge gradient policy to the contextual bandit settings. A study on how to reduce health care costs on a real world knee replacement dataset shows that we can significantly improve the success rates. Since the high sparsity and the relatively small number of patients makes leaning more difficult, with the adaptation of an online boosting framework, we further develop hierarchical knowledge-gradient policies to sequentially make decisions in high-dimensional settings while balancing the contribution of each level of feature aggregation.

1 0

Mehmet Basbug will present his FPO "Integrating Exponential Dispersion Models to Latent Structures" on Tuesday, January 10, 2017 at 1pm in CS401
by Nicki Gotsis 03 Jan '17

03 Jan '17

Department of Electrical Engineering Final Public Oral Examination of Mehmet Basbug Integrating Exponential Dispersion Models to Latent Structures Tuesday, January 10, 2017 Room 401CS Computer Science Building 1:00 PM All those interested are welcome to attend. Advisers: Robert E. Schapire and Barbara E. Engelhardt Non-technical Abstract: "Latent variable models have two basic components: a latent structure encoding a hypothesized complex pattern and an observation model capturing the data distribution. With the advancements in machine learning and increasing availability of resources, we are able to perform inference in deeper and more sophisticated latent variable models. In most cases, these models are designed with a particular application in mind; hence, they tend to have restrictive observation models. The challenge, surfaced with the increasing diversity of data sets, is to generalize these latent models to work with different data types. We aim to address this problem by utilizing exponential dispersion models (EDMs) and proposing mechanisms for incorporating them into latent structures. First, we show that the common EDM families can be expressed as a divergence from its mean in the dual domain. In particular, we argue that each EDM family induces a unique topology. For example, the Gaussian family relates to the Euclidean topology. We parametrize classes of EDM families in terms of the induced topology. We then propose an adaptive algorithm (AdaCluster) for clustering heterogeneous data sets. AdaCluster can, for instance, identify if the underlying distribution of a multi-modal positive continuous attribute is gamma, Gaussian or inverse-Gaussian. Next, we generalize a Bayesian non-negative matrix factorization model (Poisson factorization) to various data types using EDMs. Poisson factorization has been successfully used to uncover the activity patterns in large scale problems like the Netflix recommendation problem. We extend the original model to other domains such as genomics and finance. Furthermore, our model decouples the preference and activity patterns–effectively distinguishing how much someone is interested in seeing a given movie and what rating she would give to the movie. Lastly, we use the Poisson factorization and EDMs within the context of missing data. We show that an arbitrary data-generating model with EDM output–such as Gaussian mixture model, probabilistic matrix factorization, Poisson mixture model or linear regression model–can be coupled with a Poisson factorization encoding the missing-data pattern. In particular, we argue that the heteroscedastic impact of missing-data pattern on the dispersion of observation variable can be captured with the proposed model." “Please click on the attached .ics file to add this event to your calendar.”

1 0

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