Abstract:
The online matching problem has received significant attention in recent years because of its connections to allocation problems in Internet advertising, crowd-sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations; rather it is to maximize the number of “successful” allocations, where success of an allocation is governed by a stochastic process which follows the allocation. Such applications motivate us to introduce stochastic rewards in the online matching problem. The bulk of the talk will focus on a deterministic algorithm for this problem whose competitive ratio converges to (approximately) 0.567 for uniform and vanishing success probabilities. If time permits, I will also talk about a randomized algorithm and an upper bound on the competitive ratio for this problem. The talk will be self-contained and is based on joint work with Aranyak Mehta.
Hosted by: Pankaj Agarwal
http://www.cs.duke.edu/events/?id=00000001539

Abstract:
Tremendous amounts of personal data about individuals are being collected and shared online. In many cases, adversaries can infer sensitive information about individuals (from such data) by utilizing auxiliary knowledge about the individuals in the data. Recent research, culminating in the development of a powerful notion called differential privacy, have transformed the field of data privacy from a black art into a rigorous mathematical discipline. One of the attractive features of differential privacy is that it is purportedly agnostic to the auxiliary information an adversary can use to breach privacy of individuals.

In this talk I will present Pufferfish, an alternate rigorous semantic approach to defining privacy which explicitly defines which information is kept secret, what adversaries (and auxiliary information) are tolerated, and bounds the information disclosed about each secret to each adversary. This framework provides a complete characterization of the privacy protection guaranteed by differential privacy. This framework highlights three important shortcomings of differential privacy that make it unsuitable for many real world applications -- it can't protect against adversaries who know about correlations in the data (like in social networks), there are fundamental limits on the utility of the data output by differentially private mechanisms, and it does not allow different levels of privacy protection for different individuals. I will present some initial ideas towards overcoming these limitations of differential privacy.

Abstract:
October 12 Friday. 7:00 p.m. Fall break begins
October 17 Wednesday. 8:30 a.m. Classes resume

Abstract:
With the advent of social networks such as Facebook, Twitter, and LinkedIn, and online offers/deals web sites, network externalties raise the possibility of marketing and advertising to users based on influence they derive from their neighbors in such networks. Indeed, a user’s valuation for a product is changed by his knowledge of which of his neighbors likes or owns the product. Designing allocation schemes and auctions in the presence of network externalities is not very well understood, and poses many challenges that are hard to address with traditional techniques. We show that even in very simple settings, optimal auction design becomes APX-Hard, and pricing schemes may not admit to Nash equilibria in buyer behavior. On the positive side, we present approximation algorithms for welfare and revenue maximization in both single item and multi-item settings via interesting linear programming relaxations.

Joint work with Anand Bhalgat and Sreenivas Gollapudi (EC 2012); and with Nima Haghpanah, Nicole Immorlica, and Vahab Mirrokni (EC 2011).

Abstract:
TBD

Abstract:

The field of `Applied Algebraic Topology' focuses on applying algebraic topology methods to study features of surfaces and functions arising in engineering scenarios, as well as for data analysis and manifold learning. This field has generated considerable interest over the past few years. However, despite the fact that many of the problems in this area involve random data collection, its probabilistic foundations are still at a very preliminary stage. This study is part of a general effort to supply applied topology methods with probabilistic statements.

A simplicial complex is a collection of vertices, edges, triangles, and simplexes of higher dimension, and one can think of it as a generalization of a graph. In a geometric complex, the presence of simplexes is determined by geometric properties of the vertices. Thus, choosing vertices at random yields a random topological space with many interesting features. We focus on the limiting behavior of the Betti numbers of such complexes (i.e. the number of k-dimensional 'holes'), as the number of vertices goes to infinity. We study different ways to construct a geometric complex, each resulting in a completely different structure.