- talks - lists.cs.princeton.edu

Friday, 12p, Sherrerd 306 - Paul Schmitt, UC Santa Barbara on Mobile Networking in Syrian Refugee Camps
by Nick Feamster 13 Jan '17

13 Jan '17

Mobile Networking in Resource-Limited Environments Paul Schmitt (http://cs.ucsb.edu/~pschmitt/), UC Santa Barbara Friday, January 13, 12p Sherrerd Hall 306 (Conference Room) Abstract: Modern networks face an unrelenting demand for high-bandwidth Internet and cellular connectivity. The challenges of providing such connectivity are exacerbated in resource-limited environments, where infrastructure improvement or augmentation is often economically infeasible. Without access to adequate connectivity, the information and technology digital divide between the ‘haves’ and ‘have-nots’ widens. In order for wireless and mobile networks to maintain pace with demand, and achieve global connectivity, we must empirically study existing resource-constrained networks and leverage those findings to inform new system designs across the telecommunications hierarchy. In this talk, I will present a cellular measurement study conducted in a Syrian refugee camp in Jordan and a hybrid cellular system, informed by the measurement campaign, designed to alleviate user-facing resource congestion on commercial cellular networks using a non-cooperative local cellular network. Signup to chat with Paul: https://docs.google.com/spreadsheets/d/1Y6YPmVBk8aUce_a5IUGgqBkE9enH1dc_d-f…

1 1

Laura Roberts will present her General Exam on January 17, 2017 at 10:15am in CS 302.
by Nicki Gotsis 10 Jan '17

10 Jan '17

Laura Roberts will present her General Exam on January 17, 2017 at 10:15am in CS 302. The members of her committee are Nick Feamster (acting adviser), Jennifer Rexford, and Arvind Narayanan. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Abstract: Previous attacks that link the sender and receiver of traffic in the Tor network (“correlation attacks”) have generally relied on analyzing traffic from TCP connections. The TCP connections of a typical client application, however, are often accompanied by DNS requests and responses. This additional traffic presents more opportunities for correlation attacks. Our work quantifies how DNS traffic can make Tor users more vulnerable to correlation attacks. We investigate how incorporating DNS traffic can make existing correlation attacks more powerful and how DNS lookups can leak information to third parties about anonymous communication. We (i) develop a method to identify the DNS resolvers of Tor exit relays; (ii) develop a new set of correlation attacks (DefecTor attacks) that incorporate DNS traffic to improve precision; (iii) analyze the Internet-scale effects of these new attacks on Tor users; and (iv) develop improved methods to evaluate correlation attacks. First, we find that there exist adversaries that can mount DefecTor attacks: for example, Google’s DNS resolver observes almost 40% of all DNS requests exiting the Tor network. We also find that DNS requests often traverse ASes that the corresponding TCP connections do not transit, enabling additional ASes to gain information about Tor users’ traffic. We then show that an adversary that can mount a DefecTor attack can often determine the website that a Tor user is visiting with perfect precision, particularly for less popular websites where the set of DNS names associated with that website may be unique to the site. We also use the Tor Path Simulator (TorPS) in combination with traceroute data from vantage points co-located with Tor exit relays to estimate the power of AS-level adversaries that might mount DefecTor attacks in practice. Note: This work is accepted for NDSS 2017 and is joint work with Benjamin Greschbach, Tobias Pulls, Philipp Winter, and Nick Feamster. Reading List: - Computer Networks: A Systems Approach (5th edition) by Peterson and Davie; 2011 - Security Engineering: A Guide to Building Dependable Distributed Systems by Anderson, Chs. 1-8, 21-24; 2008 - “The Effect of DNS on Tor’s Anonymity” by Greschbach, Pulls, Roberts, Winter, and Feamster; 2017 - “Tor: The Second-Generation Onion Router” by Dingledine et al.; 2004 - “Users Get Routed: Traffic Correlation on Tor by Realistic Adversaries” by Johnson et al.; 2013 - “DNS measurements at a root server” by Brownlee et al.; 2001 - “Defending Tor from Network Adversaries: A Case Study of Network Path Prediction” by Juen et al.; 2015 - “Fingerprinting Websites Using Traffic Analysis” by Hintz; 2002 - “AS-awareness in Tor Path Selection” by Edman and Syverson; 2009 - “Location Diversity in Anonymity Networks” by Feamster and Dingledine; 2004 - “A Critical Evaluation of Website Fingerprinting Attacks” by Juarez et al.; 2014 - “Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms” by Chaum; 1981

1 0

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