Source author record

Wennan Zhu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computer Science and Game Theory Cryptography and Security

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Federated Heavy Hitters Discovery with Differential Privacy

The discovery of heavy hitters (most frequent items) in user-generated data streams drives improvements in the app and web ecosystems, but can incur substantial privacy risks if not done with care. To address these risks, we propose a distributed and privacy-preserving algorithm for discovering the heavy hitters in a population of user-generated data streams. We leverage the sampling and thresholding properties of our distributed algorithm to prove that it is inherently differentially private, without requiring additional noise. We also examine the trade-off between privacy and utility, and show that our algorithm provides excellent utility while also achieving strong privacy guarantees. A significant advantage of this approach is that it eliminates the need to centralize raw data while also avoiding the significant loss in utility incurred by local differential privacy. We validate our findings both theoretically, using worst-case analyses, and practically, using a Twitter dataset with 1.6M tweets and over 650k users. Finally, we carefully compare our approach to Apple's local differential privacy method for discovering heavy hitters.

preprint2020arXiv

Forming better stable solutions in Group Formation Games inspired by Internet Exchange Points (IXPs)

We study a coordination game motivated by the formation of Internet Exchange Points (IXPs), in which agents choose which facilities to join. Joining the same facility as other agents you communicate with has benefits, but different facilities have different costs for each agent. Thus, the players wish to join the same facilities as their "friends", but this is balanced by them not wanting to pay the cost of joining a facility. We first show that the Price of Stability ( $PoS$ ) of this game is at most 2, and more generally there always exists an $α$ -approximate equilibrium with cost at most $\frac{2}α$ of optimum. We then focus on how better stable solutions can be formed. If we allow agents to pay their neighbors to prevent them from deviating (i.e., a player $i$ voluntarily pays another player $j$ so that $j$ joins the same facility), then we provide a payment scheme which stabilizes the solution with minimum social cost $s^*$ , i.e. PoS is 1. In our main technical result, we consider how much a central coordinator would have to pay the players in order to form good stable solutions. Let $Δ$ denote the total amount of payments needed to be paid to the players in order to stabilize $s^*$ , i.e., these are payments that a player would lose if they changed their strategy from the one in $s^*$ . We prove that there is a tradeoff between $Δ$ and the Price of Stability: $\fracΔ{cost(s^*)} \le 1 - \frac{2}{5} PoS$ . Thus when there are no good stable solutions, only a small amount of extra payment is needed to stabilize $s^*$ ; and when good stable solutions already exist (i.e., $PoS$ is small), then we should be happy with those solutions instead. Finally, we consider the computational complexity of finding the optimum solution $s^*$ , and design a polynomial time $O(\log n)$ approximation algorithm for this problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.