PhD Proposal: Fairness and Scalability for Massive Networks

Talk
Marina Knittel
Time: 
12.16.2020 14:00 to 16:00
Location: 

Remote

The impact of massive data processing on our daily lives is becoming increasingly more clear. With this, we must guarantee that vital, data-driven decision-making systems mitigate the potential negative impacts of the technologies themselves and scale to the massive datasets we have access to today. We explore both of these facets by studying fairness and scalability for algorithms on large networks.In fairness, we extend Chierichetti et al.'s notion of clustering without over-representation to hierarchical clustering. Additionally, we introduce the first approximation algorithms for three well-studied hierarchical clustering optimization problems in the fair context. To explore incentive structures on networks, we present another result that extends the work of Friedkin and Johnsen to model multi-agent games of influence on networks and provide scalable algorithms to compute equilibria. We continue to study notions of fairness and incentive structures through stability in affiliated hiring markets, other aspects of our multi-agent games of influence model, and additional contexts in fair clustering.In scalability, we leverage the Massively Parallel Computation (MPC) model, as well as it's recent successor Adaptive Massively Parallel Computation (AMPC), to develop extremely efficient network algorithms for big data. MPC has been one of the most practically useful models for massively parallel algorithms in the past decade, influencing a number of major frameworks including MapReduce, Hadoop, Spark, and Flume. We present our previous results on edge coloring and hierarchical clustering in MPC, as well as future directions in sparse graph decompositions, compact embeddings of high-dimensional data, and other canonical problems in graph theory.Examining Committee:

Chair: Dr. MohammadTaghi Hajiaghayi Dept rep: Dr. David Mount Members: Dr. John Dickerson Dr. Ravi Kumar