- talks - lists.cs.princeton.edu

Seminar Reminder: Physical Knowledge Discovery in the Internet of Things. Fri. Jan 20 noon-1:30 in CS 402.
by Margaret Martonosi 20 Jan '17

20 Jan '17

Physical Knowledge Discovery in the Internet of Things Prof. Pei Zhang Carnegie Mellon University Friday Jan 20 noon-1:30 in CS 402 Abstract: In many sensing scenarios, direct sensing of desired events is difficult and often impossible. This is often due to deployment difficulties, lack of available sensors, and cost of maintenance. This talk will explore indirect sensing framework that infer information from physical inertial sensing through a combination of empirical, analytical and heuristic models. The talk then explore this framework through three projects. 1) The SensorFly system, a low-cost, miniature aerial sensor network that aims to be autonomous in deployment, maintenance and adaptation to the environment. By modeling the motion and movement, these sensors collaboratively localize and navigate indoors using inertial sensors. 2) Landing the sensors inside the building, the same sensor sets can be used to discover occupant information including location, identity, status, etc. 3) The same sensors on the human body, the system can inference muscle activity and fatigue level. The talk will explore the commonalities of data understanding and inferencing. Bio: Pei Zhang is an associate research professor in the ECE departments at Carnegie Mellon University. He received his bachelor's degree with honors from California Institute of Technology in 2002, and his Ph.D. degree in Electrical Engineering from Princeton University in 2008. While at Princeton University, he developed the ZebraNet system, which is used to track zebras in Kenya. It was the first deployed, wireless, ad- hoc, mobile sensor network. His recent work includes SensorFly (focus on groups of autonomous miniature-helicopter based sensor nodes) and MARS (Muscle Activity Recognition). Beyond research publications, his work has been featured on popular media including CNN, Science Channel, Discovery Channel, CBS News, CNET, Popular Science, BBC Focus, etc. He is also a cofounder of the startup Vibradotech. In addition, he has won several awards including the NSF CAREER, Edith and Martin B. Stein Solar Energy Innovation Award, and a member of the Department of Defense Computer Science Studies Panel. Margaret Martonosi H. T. Adams '35 Professor of Computer Science. Princeton University ■ mrm(a)princeton.edu ■ http://www.princeton.edu/~mrm

1 1

Reid Oda will present his Pre FPO January 24, 2017 in CS 402 at 12pm.
by Nicki Gotsis 18 Jan '17

18 Jan '17

Reid Oda will present his Pre FPO January 24, 2017 in CS 402 at 12pm. The members of his committee are: Rebecca Fiebrink (adviser), Adam Finkelstein, Dan Trueman (readers), Chris Chafe (Stanford), Marshini Chetty (non-readers) Everyone is invited to attend his talk. The talk abstract follow below: I will consider the problem of playing live, rhythmically synchronized, collaborative music over the Internet. Though the Internet has revolutionized many forms of communication, online collaborative musical performance has yet to become widespread. This is largely because of the latency (temporal delay) that is inherent in Internet communication, which makes it difficult for musicians to play in time with one another. In my thesis I propose two solutions to this problem, deploy them to musicians, and study them. The first approach, called the Global Metronome, allows players to play in time with one another, even if there is zero communication between them. The Global Metronome is a GPS-connected tempo-keeping device that automatically beats in time with every other Global Metronome implementation. The approach also allows for MIDI (musical instrument digital interface) clock enabled devices to be synchronized over long distances, which has not been previously possible. The second approach, MalLo, is a predictive instrument used to combat latency via prediction. By tracking a percussion mallet, MalLo predicts when a note is going to be played, and sends the timing information across a network, early, so that it can be turned into audio at the same time by both sender and receiver. Finally, I will provide a comprehensive analysis of the strengths and weaknesses of each approach and make recommendations for further advancements.

1 0

Nick Giannarakis will present his general exam on January 24, 2017 at 9:30am in CS 302.
by Nicki Gotsis 18 Jan '17

18 Jan '17

Nick Giannarakis will present his general exam on January 24, 2017 at 9:30am in CS 302. The members of his committee are: Andrew Appel (adviser), Margaret Martonosi, and David Walker. 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. Title: Semantics of well synchronized programs on weakly consistent machines. Abstract: The semantics of shared-memory concurrent programs are quite intricate. For one, optimizing compilers perform transformations that may be unsound with respect to concurrent programs. Moreover, modern multiprocessors have relaxed semantics: the widespread assumption of sequential consistency is invalidated by common architectural optimizations. Processors reorder instructions (or executes them out of order), and techniques such as caching of memory data and buffering of operations break the abstraction of a single global view of the memory shared by all threads. Programs that don’t have data races, however, should execute as if they were running on a sequentially consistent machine. In this work, we focus on a class of programs called well synchronized; access to some part of the shared memory is arbitrated by synchronizing operations and threads do not compete with each other for that memory. Using the Coq proof assistant, we formalized this notion of well synchronized programs, and used it to prove that cooperative (yield on synchronizing operations) and preemptive (interleaving) semantics of such programs coincide. Furthermore, we proved that well synchronized programs don’t have data races, hence their relaxed semantics coincides with their interleaving semantics. We prove that result in a generic and modular way, and demonstrate its applicability on the TSO memory model using the X86 ISA. Reading List: • Stability in weak memory models, Jade Alglave, Luc Maranget. In CAV 2010. • Relaxed Memory Concurrency and Verified Compilation. Jaroslav Sevcik, Viktor Vafeiadis, Francesco Zappa Nardelli, Suresh Jagannathan, Peter Sewell. In POPL 2011. • Reasoning about the Implementation of Concurrency Abstractions on x86-TSO, Scott Owens. In ECOOP 2010. • Compositional CompCert. Gordon Stewart, Lennart Beringer, Santiago Cuellar, Andrew W. Appel. In POPL 2015. • Taming Weak memory models.Sizhuo Zhang, Arvind, Muralidaran Vijayaraghavan. Draft. • Verifying read-copy-update in a logic for weak memory. Joseph Tassarotti, Derek Dreyer, Viktor Vafeiadis. In PLDI 2015. • A promising semantics for relaxed-memory concurrency. Jeehoon Kang, Chung-Kil Hur, Ori Lahav, Viktor Vafeiadis, Derek Dreyer. In POPL 2017. • Types and Programming Languages, Benjamin C. Pierce. • The Formal Semantics of Programming Languages, Glynn Winskel.

1 0

Prof. Pei Zhang. CMU. Friday Seminar Jan 20. Noon-1:30.
by Margaret Martonosi 13 Jan '17

13 Jan '17

HI folks- Pei Zhang from CMU Silicon Valley will be visiting on Friday Jan 20 and giving a seminar. During his PhD, Pei was a lead student on the Princeton ZebraNet project, and has since continued to do some very cool work in the area of mobile sensing and IoT. The seminar will be Friday Jan 20 noon-1:30 in CS 402 and I’ll provide lunch. The title/abstract/bio are below. If you are interested in having a spot on his one-on-one schedule, please let me know! Thanks very much, Margaret Title: Physical Knowledge Discovery in the Internet of Things Abstract: In many sensing scenarios, direct sensing of desired events is difficult and often impossible. This is often due to deployment difficulties, lack of available sensors, and cost of maintenance. This talk will explore indirect sensing framework that infer information from physical inertial sensing through a combination of empirical, analytical and heuristic models. The talk then explore this framework through three projects. 1) The SensorFly system, a low-cost, miniature aerial sensor network that aims to be autonomous in deployment, maintenance and adaptation to the environment. By modeling the motion and movement, these sensors collaboratively localize and navigate indoors using inertial sensors. 2) Landing the sensors inside the building, the same sensor sets can be used to discover occupant information including location, identity, status, etc. 3) The same sensors on the human body, the system can inference muscle activity and fatigue level. The talk will explore the commonalities of data understanding and inferencing. Bio: Pei Zhang is an associate research professor in the ECE departments at Carnegie Mellon University. He received his bachelor's degree with honors from California Institute of Technology in 2002, and his Ph.D. degree in Electrical Engineering from Princeton University in 2008. While at Princeton University, he developed the ZebraNet system, which is used to track zebras in Kenya. It was the first deployed, wireless, ad- hoc, mobile sensor network. His recent work includes SensorFly (focus on groups of autonomous miniature-helicopter based sensor nodes) and MARS (Muscle Activity Recognition). Beyond research publications, his work has been featured on popular media including CNN, Science Channel, Discovery Channel, CBS News, CNET, Popular Science, BBC Focus, etc. He is also a cofounder of the startup Vibradotech. In addition, he has won several awards including the NSF CAREER, Edith and Martin B. Stein Solar Energy Innovation Award, and a member of the Department of Defense Computer Science Studies Panel. Margaret Martonosi H. T. Adams '35 Professor of Computer Science. Princeton University ■ mrm(a)princeton.edu ■ http://www.princeton.edu/~mrm

1 0

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