Seminars

Title: TWO QUANTITATIVE STUDIES CONCERNING VOTING SYSTEMS

Speaker: Prof. Allan Borodin (University of Toronto) 

When: Thursday, 12 December 2019
Where: DIAG, Via Ariosto 25, Room B203 

Abstract:

There is a current societal interest in social choice theory (e.g. voting systems) motivated at least in part by the divisiveness apparent in many countries. Can computer science and AI bring any insight into some of the more prominent issues?     More specifically, recent elections in the US and Canada (and elsewhere)  have brought to prominence a couple of issues, Gerrymamdering and the role of primaries in voting.  (Voting goes beyond political elections but political elections are the most newsworthy.) As one can imagine, there are complex modeling and computational issues when dealing with large social and political systems.
 
We have some preliminary but we think interesting insights into gerrymandering (strategic design of electoral districts) and primary systems. I will briefly talk about a work at IJCAI 2018 on gerrymandering and how the ``power of gerrymadering'' relates to the degree of urbanization. I will mainly talk about the issue of primaries vs direct elections as our work here is a blend of both theory and experimental work. Here is the basic question: What is the impact on the ``quality'' of our chosen leaders by having primaries where each party has its own election to choose their candidate for the general election? Does this tend to result in more extreme candidates?  In a paper at AAAI 2019 paper on primaries, we conduct the first quantitative study of primary vs direct elections.

 

Joint work with Omer Lev, Nisarg Shah and Tyrone Strangway

 
Title: GRAPH CLUSTERING WITH NOISY QUERIES AND MOTIFS

Speaker: Charalampos Tsourakakis (Boston University and Harvard)

 

When: December 9, 2019 h12:00
Where:Aula Magna, DIAG, VIA Ariosto 25

 

Abstract:

Graph clustering is a fundamental problem in graph mining with important applications ranging from social networks analysis and entity resolution to computer vision and semi-supervised learning. In this talk I will discuss two novel variations of graph clustering. In the first part of the talk I will discuss the following clustering problem: there exist two latent clusters, and we are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability less than 1/2. Can we recover the clusters with high probability and what is the minimum number of queries needed? I will present two state-of-the-art algorithms and a closely related application on predicting signs in online social networks. Our results improve recent results by Mazumdar and Saha [NIPS’17]. In the second part of the talk, I will discuss how to exploit motifs to uncover communities. Specifically, I will introduce the concept of motif-expanders that serves as the basis for motif-based clustering. I will present efficient algorithms and a well-performing heuristic that outperforms some of the most popular graph clustering tools. I will conclude with some experimental results that show the effectiveness of our methods to multiple applications in machine learning and graph mining.

Bio
Babis Tsourakakis is an assistant professor in computer science at Boston University and a research associate at Harvard. Tsourakakis obtained his PhD in Algorithms, Combinatorics and Optimization at Carnegie Mellon under the supervision of Alan Frieze, was a postdoctoral fellow at Brown University and Harvard under the supervision of Eli Upfal and Michael Mitzenmacher respectively. Before joining Boston University, he worked as a researcher in the Google Brain team. He won a best paper award in IEEE Data Mining, has delivered three tutorials in the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, and has designed two graph mining libraries for large-scale graph mining, one of which has been officially included in Windows Azure. His research focuses on large-scale graph mining, and machine learning.