Upcoming events

Constrained Counting and Sampling: Bridging the Gap between Theory and Practice

Kuldeep Meel
Rice University
SWS Colloquium
07 Mar 2017, 10:00 am - 12:30 pm
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 111
Constrained counting and sampling are two fundamental problems in Computer Science with numerous applications including network reliability privacy probabilistic reasoning and constrained-random verification. In constrained counting the task is to compute the total weight subject to a given weighting function of the set of solutions of the given constraints. In constrained sampling the task is to sample randomly subject to a given weighting function from the set of solutions to a set of given constraints. In this talk I will introduce a novel algorithmic framework for constrained sampling and counting that combines the classical algorithmic technique of universal hashing with the dramatic progress made in Boolean reasoning over the past two decades. This has allowed us to obtain breakthrough results in constrained sampling and counting providing a new algorithmic toolbox in machine learning probabilistic reasoning privacy and design verification. I will demonstrate the utility of the above techniques on various real applications including probabilistic inference design verification and our ongoing collaboration in estimating the reliability of critical infrastructure networks during natural disasters.

Randomized Algorithms Meets Formal Verification

Justin Hsu
University of Pennsylvania
SWS Colloquium
08 Mar 2017, 10:00 am - 12:30 pm
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 111
Algorithms and formal verification are two classical areas of computer science. The two fields apply rigorous mathematical proof to seemingly disparate ends---on the one hand analyzing computational efficiency of algorithms; on the other designing techniques to mechanically show that programs are correct.

In this talk I will present a surprising confluence of ideas from these two areas. First I will show how coupling proofs used to analyze random walks and Markov chains correspond to proofs in the program logic pRHL (probabilistic Relational Hoare Logic). This connection enables formal verification of novel probabilistic properties and provides an structured understanding of proofs by coupling. Then I will show how an approximate version of pRHL called apRHL points to a new approximate version of couplings closely related to differential privacy. The corresponding proof technique---proof by approximate coupling---enables cleaner proofs of differential privacy both for humans and for formal verification. Finally I will share some directions towards a possible "Theory AB" blending ideas from both worlds.

Privacy as a Service

Raymond Cheng
University of Washington
SWS Colloquium
13 Mar 2017, 10:30 am - 1:00 pm
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 111
Current cloud services are vulnerable to hacks and surveillance programs that undermine user privacy and personal liberties. In this talk I present how we can build practical systems for protecting user privacy from powerful persistent threats. I will discuss Talek a private publish-subscribe protocol. With Talek application developers can send and synchronize data through the cloud without revealing any information about data contents or communication patterns of application users. The protocol is designed with provable security guarantees and practical performance 3-4 orders of magnitude better throughput than other systems with comparable security goals. I will also discuss Radiatus a security-focused web framework to protect web apps against external intrusions and uProxy a Internet censorship circumvention tool in deployment today.

Recent events

Variational Bayes In Private Settings

Mijung Park
Amsterdam Machine Learning Lab
SWS Colloquium
03 Mar 2017, 10:00 am - 11:00 am
Kaiserslautern building G26, room 111
simultaneous videocast to Saarbrücken building E1 5, room 029
Bayesian methods are frequently used for analysing privacy-sensitive datasets including medical records emails and educational data and there is a growing need for practical Bayesian inference algorithms that protect the privacy of individuals' data. To this end we provide a general framework for privacy-preserving variational Bayes (VB) for a large class of probabilistic models called the conjugate exponential (CE) family. Our primary observation is that when models are in the CE family we can privatise the variational posterior distributions simply by perturbing the expected sufficient statistics of the complete-data likelihood. For widely used non-CE models with binomial likelihoods (e.g. logistic regression) we exploit the Polya-Gamma data augmentation scheme to bring such models into the CE family such that inferences in the modified model resemble the original (private) variational Bayes algorithm as closely as possible. The iterative nature of variational Bayes presents a further challenge for privacy preservation as each iteration increases the amount of noise needed. We overcome this challenge by combining: (1) a relaxed notion of differential privacy called concentrated differential privacy which provides a tight bound on the privacy cost of multiple VB iterations and thus significantly decreases the amount of additive noise; and (2) the privacy amplification effect of subsampling mini-batches from large-scale data in stochastic learning. We empirically demonstrate the effectiveness of our method in CE and non-CE models including latent Dirichlet allocation (LDA) Bayesian logistic regression and Sigmoid Belief Networks (SBNs) evaluated on real-world datasets. >

The Diffix Framework: Noise Revisited, Again

Paul Francis
Max Planck Institute for Software Systems
Joint Lecture Series
01 Mar 2017, 12:15 pm - 2:15 pm
Saarbrücken building E1 5, room 002
A longstanding open problem in Computer Science is that of how to get high quality statistics through direct queries to databases containing information about individuals without revealing information specific to those individuals.  It has long been recognized that the key to making this work is to add noise to query answers.  The problem has been how to do this without either adding a great deal of noise to answers or limiting the number of answers an analyst can obtain.  This talk presents Diffix a new framework for anonymous database query.  Diffix adds noise in such a way that repeated answers produce the same noise: it cannot be averaged away.  This "fixed noise" mechanism however creates new opportunities for attacks.  Diffix pro-actively tests potential alternate queries to discover and prevent these attacks.  In this talk we describe the Diffix framework and present a system design that provides basic query logic and statistical operations.  We will give a brief demo of a more advanced Diffix system that operates as a commercial product.  

Learning With and From People

Adish Singla
ETH Zürich
SWS Colloquium
28 Feb 2017, 10:00 am - 11:00 am
Kaiserslautern building G26, room 111
simultaneous videocast to Saarbrücken building E1 5, room 029
People are becoming an integral part of computational systems fueled primarily by recent technological advancements as well as deep-seated economic and societal changes. Consequently there is a pressing need to design new data science and machine learning frameworks that can tackle challenges arising from human participation (e.g. questions about incentives and users? privacy) and can leverage people?s capabilities (e.g. ability to learn).

In this talk I will share my research efforts at the confluence of people and computing to address real-world problems. Specifically I will focus on collaborative consumption systems (e.g. shared mobility systems and sharing economy marketplaces like Airbnb) and showcase the need to actively engage users for shaping the demand who would otherwise act primarily in their own interest. The main idea of engaging users is to incentivize them to switch to alternate choices that would improve the system?s effectiveness. To offer optimized incentives I will present novel multi-armed bandit algorithms and online learning methods in structured spaces for learning users? costs for switching between different pairs of available choices. Furthermore to tackle the challenges of data sparsity and to speed up learning I will introduce hemimetrics as a structural constraint over users? preferences. I will show experimental results of applying the proposed algorithms on two real-world applications: incentivizing users to explore unreviewed hosts on services like Airbnb and tackling the imbalance problem in bike sharing systems. In collaboration with an ETH Zurich spinoff and a public transport operator in the city of Mainz Germany we deployed these algorithms via a smartphone app among users of a bike sharing system. I will share the findings from this deployment.