CS Colloquium Series @ UCY
Department of Computer Science - University of Cyprus
The Department of Computer Science at the University of Cyprus holds research colloquiums and social hours approximately once weekly. All university students, faculty, and staff are invited to attend. Notifications about new and upcoming events are automatically disseminated to a variety of institutional lists.
If you don't receive these notifications, but want to get informed about upcoming colloquium announcements, you can do the following:
List
RSS
Directions
Colloquium Coordinator: Demetris Zeinalipour
Colloquium: Optimal learning of joint alignments, Dr. Charalampos E. Tsourakakis (Boston University, USA), Wednesday, December 11, 2019, 10:00-11:00 EET.
The Department of Computer Science at the University of Cyprus cordially invites you to the Colloquium entitled:
Optimal learning of joint alignments
 |
Speaker: Dr. Charalampos E. Tsourakakis |
Abstract:
We consider the following problem, which is useful in applications such as joint image and shape alignment. The goal is to recover
n discrete variables $g_i \in \{0, \ldots, k-1\}$ (up to some global offset) given noisy observations of a set of their pairwise
differences $\{g_i - g_j \bmod k\}$; specifically, with probability $\frac{1}{k}+\delta$ for some $\delta > 0$ one obtains the correct
answer, and with the remaining probability one obtains a uniformly random incorrect answer. We consider a learning-based formulation
where one can perform a query to observe a pairwise difference, and the goal is to perform as few queries as possible while obtaining the
exact joint alignment. We provide an easy-to-implement, time efficient algorithm that performs $O(n \lg n/\delta^2 k)$ queries, and recovers the
joint alignment with high probability. We also show that our algorithm is optimal. This work improves significantly work of Chen and Candes,
who view the problem as a constrained principal components analysis problem that can be solved using the power method. Our approach is simpler both in the algorithm and the
analysis, and provides additional insights into the problem structure. Finally, experimentally our algorithm performs well compared to the algorithm of Chen
and Candes both in terms of accuracy and running time.
Joint work with Kasper Green Larsen and Michael Mitzenmacher
Short 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.
 | Recording: https://www.youtube.com/watch?v=P_JL8CBn2_E&t=56s |
Colloquium: Risk averse graph mining, Dr. Charalampos Tsourakakis (Boston University, USA), Friday, May 10, 2019, 12:00-13:00 EET.
The Department of Computer Science at the University of Cyprus cordially invites you to the Colloquium entitled:
Risk averse graph mining
 |
Speaker: Dr. Charalampos Tsourakakis |
Abstract:
Uncertain graphs model various important real-world settings, ranging from influence maximization, and entity resolution to protein interactions, and kidney exchanges. Mining such graphs poses significant challenges. Simple graph queries on deterministic graphs may become NP-hard, or even #P-complete on uncertain graphs, and furthermore even if we could find the optimal solutions in expectation, these may involve significant risk. In this talk we will present recent contributions to finding risk-averse (i) maximum matchings in uncertain graphs, (ii) dense subgraphs. Our algorithmic primitives in contrast to existing risk averse algorithmic approaches are time-, and space- efficient, and come with solid approximation guarantees. We evaluate our methods on a variety of real-world uncertain graphs where we observe interesting trade-offs between risk and reward.
Short Bio:
Charalampos Tsourakakis is an assistant professor in computer science at Boston University and a research associate at Harvard. Dr. 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 has received the 10-year highest impact paper award from IEEE, has 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.
Note:
Joint work with Tianyi Chen (Boston University), Johnson Lam (Boston University), Shreyas Sekar (Harvard), Naonori Kakimura (Keio University) and Jakub Pachocki (OpenAI).