Theory Day in Taiwan (2016B)

Mark Bun

Title: Make Up Your Mind: The Price of Online Queries in Differential Privacy

---

Abstract: We consider the problem of answering queries about a sensitive dataset subject to differential privacy. The queries may be chosen adversarially from a larger set of allowable queries in one of three ways, which we list in order from easiest to hardest to answer:

Offline: The queries are chosen all at once and the differentially private mechanism answers the queries in a single batch.

Online: The queries are chosen all at once, but the mechanism only receives the queries in a streaming fashion and must answer each query before seeing the next query.

Adaptive: The queries are chosen one at a time and the mechanism must answer each query before the next query is chosen. In particular, each query may depend on the answers given to previous queries.

Many differentially private mechanisms are just as efficient in the adaptive model as they are in the offline model. Meanwhile, most lower bounds for differential privacy hold in the offline setting. This suggests that the three models may be equivalent.

We prove that these models are all, in fact, distinct. Specifically, we show that there is a family of statistical queries such that exponentially more queries from this family can be answered in the offline model than in the online model. We also exhibit a family of search queries such that exponentially more queries from this family can be answered in the online model than in the adaptive model. We also investigate whether such separations might hold for simple queries, such as threshold queries over the real line.

Joint work with Thomas Steinke and Jonathan Ullman.

Georgios Piliouras

Title: Learning in Games and the Topology of Dynamical Systems

---

Abstract: Nash's proof of equilibrium existence has offered a tool of seminal importance to economic theory, however, important hurdles remain. First, learning does not necessarily converge to Nash equilibria. Furthermore, even in classes of games where learning does converge (e.g. potential games) typically many equilibria with quite different properties exist. We introduce tools from topology of dynamical systems to address these challenges. For general games, we introduce a new notion that generalizes Nash equilibria and captures formally the notion of recurrent behavior. For potential games, where learning does converge, we show how to formally define and compute the notion of average case system behavior where the predictions of different equilibria are weighted by their probability to arise under evolutionary dynamics given random initial conditions. We will discuss how these notions can give us a much deeper understanding of classic game theoretic settings. No prior knowledge on topology, dynamical systems or game theory will be assumed.

Based on joint works with Christos Papadimitriou (UC Berkeley) and Ioannis Panageas (GaTech).

Xin Han

Title: Black and White Bin Packing Revisited

---

Abstract: The black and white bin packing problem is a variant of the classical bin packing problem, where in addition to a size, each item also has a color (black or white), and in each bin the colors of items must alternate. The problem has been studied extensively, but the best competitive online algorithm has competitiveness of 3. The competitiveness of 3 can be forced even when the sizes of items are 'halved', i.e.~the sizes are restricted to be in (0,1/2]. We give the first `better than 3' competitive algorithm for the problem for the case that item sizes are in the range (0,1/2].

Yuichi Yoshida

Title: Higher-Order Fourier Analysis and Algebraic Property Testing

---

Abstract: Property testing aims for constant-query algorithms that distinguish objects satisfying a predetermined property from objects that are ``far'' from satisfying it. Along with the development of the higher order Fourier analysis, there has been a rapid progress in testing affine-invariant properties of functions over a finite field, including low-degree polynomials, and finally a characterization of affine-invariant properties that are testable with a constant number of queries was achieved. In this talk, we survey these results.