UMass Machine Learning and Friends Lunch | Main / Adaptive Anonymity Via B-Matching

Abstract:

In this talk we will focus on the adaptive anonymity problem and the way it can be handled by the so-called b-matching graphs. The adaptive anonymity problem is formalized where each individual shares their data along with an integer value to indicate their personal level of desired privacy. This problem leads to a generalization of k-anonymity to the b-matching setting. Novel algorithms and theory are provided to implement this type of anonymity. The relaxation achieves better utility, admits theoretical privacy guarantees that are as strong, and, most importantly, accommodates a variable level of anonymity for each individual. Empirical results confirm improved utility on benchmark and social data-sets.

Authors: Krzysztof Choromanski (Google Research), Tony Jebara (Columbia University) and Kui Tang (Columbia University).

Bio:

Krzysztof Choromanski currently working with Sanjiv Kumar - obtained his Ph.D degree from Columbia University in May 2013. He works on scalable matching project right now. He is interested in many branches of computer science and mathematics. Among them are: structural, spectral and random graph theory, machine learning and cryptography. He earned his double master degree from University of Warsaw (in both mathematics and computer science). He received several awards such as bronze medal at the International Olympiad in Physics in 2004 (Pohang, South Korea), gold medal at the International Team Regional Mathematical Contest in 2003 (Graz, Austria) and many national awards (such as: two gold medals at Polish Mathematical Olympiad, one gold medal at Polish Physics Olympiad, First Grand Prize at the Warsaw University of Technology Physics Competition). Recently he managed to prove the celebrated Erdos-Hajnal Conjecture for all tournaments on at most five vertices (the undirected analogous version is still open). He gave talks regarding structural graph theory and the Erdos-Hajnal Conjecture in several research institutions such as: Princeton University, Yale University, Rutgers University, Renyi Institute in Budapest and Google (tech talk at Mountain View).He is playing piano for more than 20 years now (Chopin being his favorite composer) and is an avid salsa dancer that started performing recently.